I've recently encountered a new (for me) notion from computational complexity theory called 3-SUM hardness which is based on the conjecture that 3-SUM problem can not be solved in $O\left(n^{2-\varepsilon}\right)$ time where $n$ is the number of reals among which we should check whether three of them sum to zero. By giving reduction from 3-SUM we get that it is unlikely that our problem could be solved in subquadratic time. From the other hand we can prove the lower bounds on the complexity of solving our problem. Then what is the difference between these two notions ? Does it just mean that giving the reduction is simpler than obtaining lower bounds or in other words we have an additional assumption (which usually remains unproved for ages :-))in our pocket that helps us prove the lower bound.
2 Answers
The reason we need complexity assumptions like the 3SUM conjecture is that we cannot prove meaningful lower bounds in any non-trivial computational models. Our best lower bounds are in bounded depth models or in monotone models, or use techniques such as diagonalization which usually apply only to somewhat contrived problems. Whereas we have exponential lower bounds on circuit size for circuits of bounded depth and for monotone circuits, the best lower bound for SAT is linear.
Since we cannot prove meaningful lower bounds on interesting problems in unrestricted computation models, we use the paradigm of reductions: assume that a specific problem is hard, and conclude that other problems are hard. The most celebrated example is, of course, the theory of NP-hardness. It is easy to criticize this methodology: the hardness assumptions that we make are sometimes controversial. Things are particularly bad in cryptography, where sometimes the hardness assumption made in a paper is a thinly veiled version of the assumption that the construction suggested in the paper works.
3SUM hardness is not a new assumption, but has recently found new interest in the community. It explains the complexity of the best known algorithms for many different problems. As such, it is coming to be viewed as the analog of NP-hardness for problems inside P. As an added bonus, 3SUM hardness makes much more accurate predictions on the complexity of problems: rather than just stating that an NP-hard problem cannot be solved in polynomial time, 3SUM hardness allows us to determine the best exponents (smallest $\alpha$ such that the problem can be solved in time $O(n^\alpha)$) of certain problems.
-
$\begingroup$ I would not base my results on the conjecture that has recently been almost refuted. Would you ? $\endgroup$– KKSApr 23, 2016 at 8:26
Currently, the only way we know to prove interesting bounds in P is through 3SUM (or other similar problems). In particular, there is no known (to my knowledge) $\Omega(n^{1+\epsilon})$ lower bound for any natural problem in NP. (There are lower bounds for artificial problems; for example determining if a Turing Machine halts in $k^3$ steps, for $k$ given in unary.) As far as we know, it's possible to solve SAT in $O(n\log n)$ time.
So your intuition is correct. It's too hard to prove a real lower bound, so we just say that we can't improve on the problem without improving on the best known 3SUM algorithm. It's similar to what we do with NP-completeness.
However, due to a fairly large amount of recent research, 3SUM is just the tip of the iceberg. Similar, and in many cases stronger, conditional lower bounds can be proven using the Strong Exponential Time Hypothesis, the Orthogonal Vectors problem, All Pairs Shortest Paths, and some others.
This survey is almost certainly the place to start, as it's written by Virginia Williams, one of the primary researchers in this field.
-
2$\begingroup$ The time hierarchy theorem contradicts this answer. We know that there exist (artificial) problems that can be solved in $O(n^2)$ time but not in $O(n^{2-\epsilon})$ time (and such problems are of course in NP, since P $\subseteq$ NP). $\endgroup$ Apr 22, 2016 at 9:25
-
$\begingroup$ We know explicit ones, or we know they exist? $\endgroup$– SamMApr 22, 2016 at 13:01
-
2$\begingroup$ We know explicit ones; whether a TM halts in $k^2$ steps ($k$ encoded in unary) is an example. $\endgroup$ Apr 22, 2016 at 15:20