# Problems that can be used to show polynomial-time hardness results

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.

• The page 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 Sep 14 '10 at 3:21
• 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 Sep 14 '10 at 3:35
• Off topic: Robin, Tsuyoshi, thanks for introducing the 3SUM family of lower bounds : I had never heard of them before. – gphilip Sep 14 '10 at 3:38
• @Tsuyoshi: Thanks for the information. This is a nice survey on the topic: 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 Sep 14 '10 at 4:43
• 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 Sep 15 '10 at 15:21

## 4 Answers

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. 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?" (At some point, "3SUM-hard" was called "$n^2$-hard"; this SIGACT article rightly complained about that name.)

• 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 Sep 14 '10 at 5:31
• 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 Sep 14 '10 at 5:50
• 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 Sep 14 '10 at 6:10
• @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 Sep 14 '10 at 6:22
• @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 Sep 15 '10 at 18:59

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.

• 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. – Raphael Nov 7 '10 at 19:43

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

• I like this answer, but could you expound? Why is it believed? – Aaron Sterling Sep 15 '10 at 14:56

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?

• are there any non-geometric problems that reduce to Hopcroft's problem ? – Suresh Venkat Sep 14 '10 at 7:13
• I decided to award the bounty to this answer because I had never heard of this problem before. – Robin Kothari Nov 12 '10 at 4:18