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

Question

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.

Answer 1

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.)

Answer 2

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.

Answer 3

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?

Answer 4

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 affine 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

Answer 5

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.