Super-linear time complexity lower bounds for any natural problem in NP? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T08:16:31Z http://mathoverflow.net/feeds/question/4953 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/4953/super-linear-time-complexity-lower-bounds-for-any-natural-problem-in-np Super-linear time complexity lower bounds for any natural problem in NP? Rune 2009-11-11T00:27:06Z 2010-06-10T15:44:25Z <p>Do we know any problem in NP which has a super-linear time complexity lower bound? Ideally, we would like to show that 3SAT has super-polynomial lower bounds, but I guess we're far away from that. I'd just like to know any examples of super-linear lower bounds.</p> <p>I know that the time hierarchy theorem gives us problems which can be solved in O(n^3) but not in O(n^2), etc. Thus I put the word "natural" in the question.</p> <p>I ask for problems in NP, because otherwise someone would give examples of EXP-complete problems. </p> <p>I know there are time-space tradeoffs for some problems in NP. I don't know if any of them imply a super-linear time complexity lower bound though.</p> <p>(To address a question below about machine models, consider either multitape Turing machines or the RAM model.)</p> http://mathoverflow.net/questions/4953/super-linear-time-complexity-lower-bounds-for-any-natural-problem-in-np/4957#4957 Answer by Sam Nead for Super-linear time complexity lower bounds for any natural problem in NP? Sam Nead 2009-11-11T00:47:34Z 2009-11-11T00:47:34Z <p>Running time depends on the model of computation. Eg the problem "Given (m, n, p) does m + n = p?" takes at least quadratic time on a one-tape Turing machine. So you can give a more reasonable model of computation... and the next person to come along will explain how it is much too strong, etc.</p> <p>Hmmm. Perhaps your question might be rephrased in terms of using some other resource (which in turn requires at least a set amount of time). So perhaps invent a decision problem around sorting, and appeal to the nlog(n) lower bound...</p> http://mathoverflow.net/questions/4953/super-linear-time-complexity-lower-bounds-for-any-natural-problem-in-np/4986#4986 Answer by Gil Kalai for Super-linear time complexity lower bounds for any natural problem in NP? Gil Kalai 2009-11-11T06:10:48Z 2009-11-11T06:10:48Z <p>The short answer is NO. The best general lower bounds are linear.</p> http://mathoverflow.net/questions/4953/super-linear-time-complexity-lower-bounds-for-any-natural-problem-in-np/9081#9081 Answer by Ryan Williams for Super-linear time complexity lower bounds for any natural problem in NP? Ryan Williams 2009-12-16T06:07:12Z 2009-12-16T06:50:04Z <p>Sorry I am so late to the discussion, but I just registered...</p> <p>There are non-linear time lower bounds on multitape Turing machines for NP-complete problems. These lower bounds follow from the fact that the class of problems solvable in nondeterministic linear time is not equal to the class of those solvable in (deterministic) linear time, in the multitape Turing machine setting. This is proved in:</p> <blockquote> <p>Wolfgang J. Paul, Nicholas Pippenger, Endre Szemerédi, William T. Trotter: On Determinism versus Non-Determinism and Related Problems (Preliminary Version) FOCS 1983: 429-438</p> </blockquote> <p>In fact, unraveling the proof shows that there must be some problem solvable in nondeterministic linear time that is not solvable in $o(n \cdot (\log^* n)^{1/4})$ time (again, on a multitape Turing machine). Note the * in the logarithm; this is just "barely" above linear. One known application of this result is that a natural NP-complete problem in automata theory cannot be solved in $o(n \cdot (\log^* n)^{1/4})$ time:</p> <blockquote> <p>Etienne Grandjean: A Nontrivial Lower Bound for an NP Problem on Automata. SIAM J. Comput. 19(3): 438-451 (1990)</p> </blockquote> <p>Unfortunately the lower bound of Paul et al. relies crucially on the geometry that arises from accessing one-dimensional tapes. We don't know how to prove a non-linear lower bound even if you allow the Turing machine to have a constant number of <b>two</b>-dimensional tapes. We can prove time lower bounds for NP problems on general computational models <i>if</i> you severely restrict the extra workspace used by the machine. (This is getting into my own work so I won't say more unless you're truly interested.)</p> <p>As for the comment above me: the sorting lower bound holds only in a comparison-based model, which is extremely restricted. The claim that sorting requires Omega(n log n) time on general computational models is false. There are faster algorithms for sorting integers. See for example:</p> <blockquote> <p>Yijie Han: Deterministic sorting in O(n log logn) time and linear space. J. Algorithms 50(1): 96-105 (2004) </p> </blockquote> http://mathoverflow.net/questions/4953/super-linear-time-complexity-lower-bounds-for-any-natural-problem-in-np/27711#27711 Answer by Timothy Chow for Super-linear time complexity lower bounds for any natural problem in NP? Timothy Chow 2010-06-10T15:44:25Z 2010-06-10T15:44:25Z <p>If you restrict <i>space</i> usage to be sublinear then you can prove superlinear <i>time</i> lower bounds on SAT. See <a href="http://rjlipton.wordpress.com/2009/04/13/sat-is-not-too-easy/" rel="nofollow">this article on Lipton's blog</a> for a nice exposition.</p>