<p>Yes, the best known algorithm for $k$-SUM runs in $O(n^{\lceil k/2 \rceil})$ time, so it's very possible that you could argue some $n^7$ problem is difficult, because if it's in $n^{6.99}$ then you can solve $14$-SUM faster. </p>

<p>Note the $k$-SUM problem gets "easier" as $k$ increases: given an improved algorithm for $k$-SUM, it's fairly easy to get an improved algorithm for $2k$-SUM: take all $O(n^2)$ pairs of $n$ numbers in your given $2k$-SUM instance, replacing each pair with the sum of the two, and look for a sum of $k$ numbers out of those that equal $0$. Then, an $O(n^{k/2-\varepsilon})$ algorithm for $k$-SUM implies an $O(n^{k-2\varepsilon})$ algorithm for $2k$-SUM. Put another way, a tight lower bound for $2k$-SUM is a stronger assumption than a tight lower bound for $k$-SUM.</p>

<p>Another candidate for a hard problem is $k$-Clique. <a href="https://cstheory.stackexchange.com/questions/609/what-are-the-best-known-upper-bounds-and-lower-bounds-for-computing-olog-n-cliq/614#614">See my $O(\log n)$-Clique answer for more on that</a>. If you can show (for example) that a better algorithm for your problem implies an $O(n^2)$ algorithm for $3$-clique, then a super-breakthrough would be required to improve on your algorithm. Parameterized complexity gives many examples of other problems like this: $k$-Clique is hard for the class $W\[1\]$, and $k$-SUM is hard for $W\[2\]$.</p>

<p>Let me warn you that although problems like this are very convenient to work with, problems like $3$-SUM are <em>not</em> among the "hardest" in $TIME[n^2]$, e.g., it is very unlikely that every problem in $TIME[n^2]$ can actually be linear-time reduced to $3$-SUM. This is because $3$-SUM can be solved with $O(\log n)$ bits of nondeterminism in linear time, so if everything in quadratic time can be reduced to $3$-SUM, then $P \neq NP$ and other fantastic consequences results. More on this point can be found in the article <a href="http://portal.acm.org/citation.cfm?id=181465" rel="noreferrer">"How hard are $n^2$-hard problems?"</a> (At some point, "3SUM-hard" was called "$n^2$-hard"; this SIGACT article rightly complained about that name.) </p>

CC BY-SA 2.5
2010-09-14T05:31:00.980Z
The only problem I have with using k-clique is that 3-clique is solvable in $O(n^2.376)$. If it were the case that k-clique seemed to require $\Theta(n^k)$, that would be a great natural family to use.
Robin Kothari
CC BY-SA 2.5
2010-09-14T05:50:23.963Z
I don't see a fundamental difference between using $k$-SUM and $k$-Clique. $k$-SUM is in $O(n^{k/2})$ for even $k$. If you can show that a better algorithm for your problem implies that $k$-Clique is in $O(n^{k/2})$, this is strong evidence that a better algorithm for your problem will be quite hard to find.
Ryan Williams
CC BY-SA 2.5
2010-09-14T06:10:22.807Z
neat reference, Ryan. I'm ashamed that I didn't know about it earlier, given how popular 3SUM is in the geometry community. Of course this begs the question: are there any natural candidates for being $n^2$ hard ?
Suresh Venkat
CC BY-SA 2.5
2010-09-14T06:22:07.033Z
@Ryan: You're right, they're the same. Although, with k-SUM, at least we have evidence in weaker models that the conjectured bound is correct. I don't know any arguments that suggest 3-clique should not be solvable faster than matrix multiplication.
Robin Kothari
CC BY-SA 2.5
2010-09-15T18:59:45.800Z
@Robin: I would have thought any natural family of problems with $n^{f(k)}$ probable lower bounds, for $f(k) = \Theta(k)$, would be a good answer.  The precise constant seems less important?
András Salamon
CC BY-SA 2.5
2010-09-15T19:38:21.213Z
@András: I was thinking of _actually_ using these problems to show hardness results, so the constants are important, or at least could be important depending on the application and the reduction used.
Robin Kothari
CC BY-SA 2.5
2010-09-14T05:20:31.983Z
2010-09-14T05:20:31.983Z
2017-04-13T12:32:30.623Z
Ryan Williams
<p>The All-Pairs Shortest Paths (APSP) problem is believed to required $\Omega^\star(n^3)$ time. Reducing from it is a great way to argue that improvements based on Fast Matrix Multiplication (FMM) are unlikely.</p>

CC BY-SA 2.5
2010-11-07T19:43:11.143Z
How about the diameter of a graph? Better yet, make it a decision problem "Is the diameter at least k?". This has the advantage of having no obvious superlinear bound, as far as I know.
Simd
CC BY-SA 2.5
2010-09-19T15:52:52.290Z
2010-09-19T15:52:52.290Z
Mihai
<p>Hopcroft's problem is conjectured to require $\Theta(n^{4/3})$ time: Given a set of $n$ points and a set of $n$ lines in the plane, does any point lie on any line?</p>

CC BY-SA 2.5
2010-09-14T07:13:24.347Z
are there any non-geometric problems that reduce to Hopcroft's problem ?
Suresh Venkat
CC BY-SA 2.5
2010-11-12T04:18:54.133Z
I decided to award the bounty to this answer because I had never heard of this problem before.
Robin Kothari
CC BY-SA 2.5
2010-09-14T06:18:00.560Z
2010-09-14T06:18:00.560Z
Jeffε
<p>It is believed that the best algorithms for the affine degeneracy problem in $d$-dimensional space run in $O(n^d)$ time. The problem is the following: Given $n$ points in $d$-dimensional space with integer coordinates, do any $d+1$ points lie on a common hyperplane?</p>

<p>The affine degeneracy problem is $(d+1)$-SUM hard. If we plug the conjectured lower bound for $k$-SUM, we  obtain a lower bound of $\Omega(n^{\lfloor d/2 \rfloor +1})$. The conjecture for the complexity of the affine degeneracy problem is much stronger for $d \geq 3$, though.</p>

<p>J. Erickson, S. Har-Peled, and D. M. Mount, On the Least Median Square Problem, Discrete and Computational Geometry, 36, 593-607, 2006. <a href="http://www.cs.umd.edu/~mount/Papers/dcg06-lms.pdf">http://www.cs.umd.edu/~mount/Papers/dcg06-lms.pdf</a></p>

<p>J. Erickson and R. Seidel. Better lower bounds on detecting aﬃne and spherical degeneracies. Discrete Comput. Geom., 13:41–57, 1995. <a href="http://compgeom.cs.uiuc.edu/~jeffe/pubs/degen.html">http://compgeom.cs.uiuc.edu/~jeffe/pubs/degen.html</a></p>

<p>J. Erickson. New lower bounds for convex hull problems in odd dimensions.
SIAM J. Comput., 28:1198–1214, 1999. <a href="http://compgeom.cs.uiuc.edu/~jeffe/pubs/convex.html">http://compgeom.cs.uiuc.edu/~jeffe/pubs/convex.html</a></p>

CC BY-SA 2.5
2010-09-15T14:56:03.240Z
I like this answer, but could you expound?  Why is it believed?
Aaron Sterling
CC BY-SA 2.5
2010-09-15T14:32:30.083Z
2010-09-15T21:33:37.977Z
2010-09-15T21:33:37.977Z
Guilherme D. da Fonseca
<p><strong>Intersection non-emptiness problem:</strong> Given two DFA's <span class="math-container">$D_1$</span> and <span class="math-container">$D_2$</span>, is <span class="math-container">$L(D_1) \cap L(D_2) \neq \emptyset$</span>?</p>

<p>This is classically known to be solvable in quadratic time by solving reachability in the Cartesian product automaton.  However, no faster algorithms are known to exist.</p>

<p>The existence of faster algorithms would imply faster algorithms for SAT: <a href="https://cstheory.stackexchange.com/a/29166/14207">https://cstheory.stackexchange.com/a/29166/14207</a></p>

<p>More generally, it is not known if we can solve intersection non-emptiness for <span class="math-container">$k$</span> DFA's in less than <span class="math-container">$O(n^k)$</span> time.</p>

CC BY-SA 4.0
2020-02-10T09:53:56.200Z
In addition, faster algorithms for intersection non-emptiness would imply faster algorithms for QBF, Triangle Finding, and OVP.  If you're interested, please let me know and I can share references and a manuscript.
Michael Wehar
CC BY-SA 4.0
2020-02-10T10:06:14.790Z
You might find this helpful as well: https://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/
Michael Wehar
CC BY-SA 4.0
2020-02-10T09:53:31.713Z
2020-02-10T09:53:31.713Z
Michael Wehar
<p>When designing an algorithm for a new problem, if I can't find a polynomial time algorithm after a while, I might try to prove it is NP-hard instead. If I succeed, I've explained why I couldn't find the polynomial time algorithm. It's not that I know for sure that P != NP, it's just that this is the best that can be done with current knowledge, and indeed the consensus is that P != NP.</p>

<p>Similarly, say I've found a polynomial-time solution for some problem, but the running time is $O(n^2)$. After a lot of effort, I make no progress in improving this. So instead, I might try to prove that it is 3SUM-hard instead. This is usually a satisfactory state of affairs, not because of my supreme belief that 3SUM does indeed require $\Theta(n^2)$ time, but because this is the current state of the art, and a lot of smart people have tried to improve it, and have failed. So it's not my fault that it's the best I can do.</p>

<p>In such cases, the best we can do is a hardness result, in lieu of an actual lower bound, since we don't have any super-linear lower bounds for Turing Machines for problems in NP.</p>

<p>Is there a uniform set of problems that can be used for all polynomial running times? For example, if I want to prove that it is unlikely that some problem has an algorithm better than $O(n^7)$, is there some problem X such that I can show it is X-hard and leave it at that?</p>

<p><strong>Update</strong>: This question originally asked for families of problems. Since there aren't that many families of problems, and this question has already received excellent examples of individual hard problems, I'm relaxing the question to any problem that can be used for polynomial-time hardness results. I'm also adding a bounty to this question to encourage more answers.</p>

CC BY-SA 3.0
2016-08-15T04:34:20.063Z
@TsuyoshiIto, that page is now at http://cs.smith.edu/~orourke/TOPP/P11.html
kodlu
CC BY-SA 2.5
2010-09-14T03:21:03.393Z
The page http://maven.smith.edu/~orourke/TOPP/P11.html summarizes some results about lower (and upper) bounds of 3SUM and related problems and is worth reading.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-14T03:35:40.067Z
The absence of super-linear lower bounds is for a TM with at least two tapes, is it not? I remember reading somewhere that checking for a palindrome on a single-tape TM has a quadratic-time lower bound.  When we talk about lower bounds _within_ $P$, of the kind $\Omega(n^i)$ vs. $\Omega(n^{i+1})$, is it still OK to assume that the exact model of TM does not matter much?
gphilip
CC BY-SA 2.5
2010-09-14T03:38:41.520Z
Off topic: Robin, Tsuyoshi, thanks for introducing the 3SUM family of lower bounds : I had never heard of them before.
gphilip
CC BY-SA 2.5
2010-09-14T04:43:47.443Z
@Tsuyoshi: Thanks for the information. This is a nice survey on the topic: http://www.cs.mcgill.ca/~jking/papers/3sumhard.pdf. @gphilip: I was recently introduced to this problem by some computational geometers. I guess it is very well known in that area.
Robin Kothari
CC BY-SA 2.5
2010-09-15T15:21:06.693Z
Great question.  Could you clarify what you mean by "uniform": do you want to bound the amount of preprocessing of the parameter?
András Salamon
<cc.complexity-theory><lower-bounds><conditional-results>
Problems that can be used to show polynomial-time hardness results
Robin Kothari
# Problems that can be used to show polynomial-time hardness results

(Asked by: username_0 on 2010-09-14)

When designing an algorithm for a new problem, if I can't find a polynomial time algorithm after a while, I might try to prove it is NP-hard instead. If I succeed, I've explained why I couldn't find the polynomial time algorithm. It's not that I know for sure that P != NP, it's just that this is the best that can be done with current knowledge, and indeed the consensus is that P != NP.

Similarly, say I've found a polynomial-time solution for some problem, but the running time is $O(n^2)$. After a lot of effort, I make no progress in improving this. So instead, I might try to prove that it is 3SUM-hard instead. This is usually a satisfactory state of affairs, not because of my supreme belief that 3SUM does indeed require $\Theta(n^2)$ time, but because this is the current state of the art, and a lot of smart people have tried to improve it, and have failed. So it's not my fault that it's the best I can do.

In such cases, the best we can do is a hardness result, in lieu of an actual lower bound, since we don't have any super-linear lower bounds for Turing Machines for problems in NP.

Is there a uniform set of problems that can be used for all polynomial running times? For example, if I want to prove that it is unlikely that some problem has an algorithm better than $O(n^7)$, is there some problem X such that I can show it is X-hard and leave it at that?

**Update**: This question originally asked for families of problems. Since there aren't that many families of problems, and this question has already received excellent examples of individual hard problems, I'm relaxing the question to any problem that can be used for polynomial-time hardness results. I'm also adding a bounty to this question to encourage more answers.

**Tags:** cc.complexity-theory, lower-bounds, conditional-results

> **Comments:**
> **username_2**: The page http://maven.smith.edu/~orourke/TOPP/P11.html summarizes some results about lower (and upper) bounds of 3SUM and related problems and is worth reading.  
> **username_3**: The absence of super-linear lower bounds is for a TM with at least two tapes, is it not? I remember reading somewhere that checking for a palindrome on a single-tape TM has a quadratic-time lower bound.  When we talk about lower bounds _within_ $P$, of the kind $\Omega(n^i)$ vs. $\Omega(n^{i+1})$, is it still OK to assume that the exact model of TM does not matter much?  
> **username_3**: Off topic: Robin, Tsuyoshi, thanks for introducing the 3SUM family of lower bounds : I had never heard of them before.  
> **username_0**: @Tsuyoshi: Thanks for the information. This is a nice survey on the topic: http://www.cs.mcgill.ca/~jking/papers/3sumhard.pdf. @username_3: I was recently introduced to this problem by some computational geometers. I guess it is very well known in that area.  
> **username_4**: Great question.  Could you clarify what you mean by "uniform": do you want to bound the amount of preprocessing of the parameter?  
> **username_1**: @TsuyoshiIto, that page is now at http://cs.smith.edu/~orourke/TOPP/P11.html  

---

## 5 answers

### Answer by username_5 on 2010-09-14. Score: 40

Yes, the best known algorithm for $k$-SUM runs in $O(n^{\lceil k/2 \rceil})$ time, so it's very possible that you could argue some $n^7$ problem is difficult, because if it's in $n^{6.99}$ then you can solve $14$-SUM faster.

Note the $k$-SUM problem gets "easier" as $k$ increases: given an improved algorithm for $k$-SUM, it's fairly easy to get an improved algorithm for $2k$-SUM: take all $O(n^2)$ pairs of $n$ numbers in your given $2k$-SUM instance, replacing each pair with the sum of the two, and look for a sum of $k$ numbers out of those that equal $0$. Then, an $O(n^{k/2-\varepsilon})$ algorithm for $k$-SUM implies an $O(n^{k-2\varepsilon})$ algorithm for $2k$-SUM. Put another way, a tight lower bound for $2k$-SUM is a stronger assumption than a tight lower bound for $k$-SUM.

Another candidate for a hard problem is $k$-Clique. [See my $O(\log n)$-Clique answer for more on that](https://cstheory.stackexchange.com/questions/609/what-are-the-best-known-upper-bounds-and-lower-bounds-for-computing-olog-n-cliq/614#614). If you can show (for example) that a better algorithm for your problem implies an $O(n^2)$ algorithm for $3$-clique, then a super-breakthrough would be required to improve on your algorithm. Parameterized complexity gives many examples of other problems like this: $k$-Clique is hard for the class $W\[1\]$, and $k$-SUM is hard for $W\[2\]$.

Let me warn you that although problems like this are very convenient to work with, problems like $3$-SUM are *not* among the "hardest" in $TIME[n^2]$, e.g., it is very unlikely that every problem in $TIME[n^2]$ can actually be linear-time reduced to $3$-SUM. This is because $3$-SUM can be solved with $O(\log n)$ bits of nondeterminism in linear time, so if everything in quadratic time can be reduced to $3$-SUM, then $P \neq NP$ and other fantastic consequences results. More on this point can be found in the article ["How hard are $n^2$-hard problems?"](http://portal.acm.org/citation.cfm?id=181465) (At some point, "3SUM-hard" was called "$n^2$-hard"; this SIGACT article rightly complained about that name.)

> **Comments:**
> **username_0**: The only problem I have with using k-clique is that 3-clique is solvable in $O(n^2.376)$. If it were the case that k-clique seemed to require $\Theta(n^k)$, that would be a great natural family to use.  
> **username_5**: I don't see a fundamental difference between using $k$-SUM and $k$-Clique. $k$-SUM is in $O(n^{k/2})$ for even $k$. If you can show that a better algorithm for your problem implies that $k$-Clique is in $O(n^{k/2})$, this is strong evidence that a better algorithm for your problem will be quite hard to find.  
> **username_6**: neat reference, Ryan. I'm ashamed that I didn't know about it earlier, given how popular 3SUM is in the geometry community. Of course this begs the question: are there any natural candidates for being $n^2$ hard ?  
> **username_0**: @Ryan: You're right, they're the same. Although, with k-SUM, at least we have evidence in weaker models that the conjectured bound is correct. I don't know any arguments that suggest 3-clique should not be solvable faster than matrix multiplication.  
> **username_4**: @Robin: I would have thought any natural family of problems with $n^{f(k)}$ probable lower bounds, for $f(k) = \Theta(k)$, would be a good answer.  The precise constant seems less important?  
> **username_0**: @András: I was thinking of _actually_ using these problems to show hardness results, so the constants are important, or at least could be important depending on the application and the reduction used.  

---

### Answer by username_7 on 2010-09-19. Score: 14

The All-Pairs Shortest Paths (APSP) problem is believed to required $\Omega^\star(n^3)$ time. Reducing from it is a great way to argue that improvements based on Fast Matrix Multiplication (FMM) are unlikely.

> **Comments:**
> **username_8**: How about the diameter of a graph? Better yet, make it a decision problem "Is the diameter at least k?". This has the advantage of having no obvious superlinear bound, as far as I know.  

---

### Answer by username_9 on 2010-09-14. Score: 10

Hopcroft's problem is conjectured to require $\Theta(n^{4/3})$ time: Given a set of $n$ points and a set of $n$ lines in the plane, does any point lie on any line?

> **Comments:**
> **username_6**: are there any non-geometric problems that reduce to Hopcroft's problem ?  
> **username_0**: I decided to award the bounty to this answer because I had never heard of this problem before.  

---

### Answer by username_10 on 2010-09-15. Score: 10

It is believed that the best algorithms for the affine degeneracy problem in $d$-dimensional space run in $O(n^d)$ time. The problem is the following: Given $n$ points in $d$-dimensional space with integer coordinates, do any $d+1$ points lie on a common hyperplane?

The affine degeneracy problem is $(d+1)$-SUM hard. If we plug the conjectured lower bound for $k$-SUM, we obtain a lower bound of $\Omega(n^{\lfloor d/2 \rfloor +1})$. The conjecture for the complexity of the affine degeneracy problem is much stronger for $d \geq 3$, though.

J. Erickson, S. Har-Peled, and D. M. Mount, On the Least Median Square Problem, Discrete and Computational Geometry, 36, 593-607, 2006. <http://www.cs.umd.edu/~mount/Papers/dcg06-lms.pdf>

J. Erickson and R. Seidel. Better lower bounds on detecting aﬃne and spherical degeneracies. Discrete Comput. Geom., 13:41–57, 1995. <http://compgeom.cs.uiuc.edu/~jeffe/pubs/degen.html>

J. Erickson. New lower bounds for convex hull problems in odd dimensions.
SIAM J. Comput., 28:1198–1214, 1999. <http://compgeom.cs.uiuc.edu/~jeffe/pubs/convex.html>

> **Comments:**
> **username_11**: I like this answer, but could you expound?  Why is it believed?  

---

### Answer by username_12 on 2020-02-10. Score: 1

**Intersection non-emptiness problem:** Given two DFA's $D\_1$ and $D\_2$, is $L(D\_1) \cap L(D\_2) \neq \emptyset$?

This is classically known to be solvable in quadratic time by solving reachability in the Cartesian product automaton. However, no faster algorithms are known to exist.

The existence of faster algorithms would imply faster algorithms for SAT: <https://cstheory.stackexchange.com/a/29166/14207>

More generally, it is not known if we can solve intersection non-emptiness for $k$ DFA's in less than $O(n^k)$ time.

> **Comments:**
> **username_12**: In addition, faster algorithms for intersection non-emptiness would imply faster algorithms for QBF, Triangle Finding, and OVP.  If you're interested, please let me know and I can share references and a manuscript.  
> **username_12**: You might find this helpful as well: https://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/  

---

