24
$\begingroup$

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.

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.

I ask for problems in NP, because otherwise someone would give examples of EXP-complete problems.

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.

(To address a question below about machine models, consider either multitape Turing machines or the RAM model.)

Improve this question
$\endgroup$

4 Answers 4

Reset to default
29
$\begingroup$

Sorry I am so late to the discussion, but I just registered...

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:

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

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:

Etienne Grandjean: A Nontrivial Lower Bound for an NP Problem on Automata. SIAM J. Comput. 19(3): 438-451 (1990)

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 two-dimensional tapes. We can prove time lower bounds for NP problems on general computational models if 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.)

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:

Yijie Han: Deterministic sorting in O(n log logn) time and linear space. J. Algorithms 50(1): 96-105 (2004)

Improve this answer
$\endgroup$
5
  • $\begingroup$ That's very interesting. Thanks. I keep hearing these lower bounds for problems in NP which establish bounds like 4n or 5n, perhaps that's a different model then. I guess the model you mention is weaker than the random-access Turing machine model, right? When you speak of restricting extra work space, is this related to the time-space trade-off results, like the paper by Fortnow? $\endgroup$
    – Rune
    Commented Dec 18, 2009 at 4:34
  • 3
    $\begingroup$ The bounds of the form 4n and 5n are for Boolean circuits with AND, OR, and NOT gates. Those lower bounds are much harder to come by. One big reason is that the Boolean circuit model is <i>non-uniform</u>, meaning that for each input length n, one has a different "program" which works for all strings of length n. Such a model can compute some non-recursive functions! The multi-tape Turing machine model certainly seems weaker than the random-access Turing machine, but this isn't known for sure. My other comment was indeed referring to the work on time-space tradeoffs. $\endgroup$
    – Ryan Williams
    Commented Dec 18, 2009 at 9:07
  • $\begingroup$ @RyanWilliams Is there evidence weakness of multitape machines within standard axioms? $\endgroup$
    – Turbo
    Commented Aug 2, 2015 at 4:59
  • $\begingroup$ @RyanWilliams , I suppose that for random access Turing machines the best known lower bounds are linear, right? $\endgroup$
    – Gil Kalai
    Commented Dec 25, 2019 at 12:28
  • $\begingroup$ For problems like SAT,, yes the best time lower bounds are linear. But of course the time hierarchy theorem (for random access machines) tells us there are problems in NTIME(n^2) on random access machines which can't be solved in subquadratic time. $\endgroup$
    – Ryan Williams
    Commented Jan 8, 2020 at 14:58
5
$\begingroup$

If you restrict space usage to be sublinear then you can prove superlinear time lower bounds on SAT. See this article on Lipton's blog for a nice exposition.

Improve this answer
$\endgroup$
4
$\begingroup$

For the circuit model, the answer is NO. The best general lower bounds are linear.

(As Ryan explained in his answer and comment for multi tape Turing machines there are (slightly) superlinear bounds. As far as I understand from his comment for random access Turing machines there are no superlinear lower bounds known.)

Improve this answer
$\endgroup$
7
  • $\begingroup$ Could you flesh this out? Or give a link to a reference? Why is finding super-linear lower bounds hard? If it is obvious, I apologize in advance. $\endgroup$
    – Sam Nead
    Commented Nov 14, 2009 at 22:23
  • 1
    $\begingroup$ Here is a citation and a link : Uri Zwick, A 4n lower bound on the combinatorial complexity of certain symmetric Boolean functions over the basis of unate dyadic Boolean functions SIAM Journal on Computing 20, 499-505 (1991) An explicit lower bound of 5n-o (n) for boolean circuits, K Iwama, O. Lachish, H Morizumi, and R. Raz springerlink.com/index/XCP1TCRY1C236RDT.pdf The introduction of the second paper and the slow incremental improvements may give some idea on the difficulty of the problem. $\endgroup$
    – Gil Kalai
    Commented Nov 21, 2009 at 14:20
  • $\begingroup$ -1: Your answer concerns nonuniform circuit families, not Turing machines or RAMs. $\endgroup$
    – Hermann Gruber
    Commented Dec 24, 2019 at 8:59
  • $\begingroup$ @HermannGruber yes indeed my answer was based on what I know for circuits (as elaborated in my comment). But I believe nothing better is known for the (general) Turing machine model. If you know otherwise please let us know. In any case the circuit model is important so the answer is very relevant to the question. $\endgroup$
    – Gil Kalai
    Commented Dec 24, 2019 at 10:58
  • 1
    $\begingroup$ @HermannGruber, I suppose that for random access Turing machines the best known lower bounds are linear, right? $\endgroup$
    – Gil Kalai
    Commented Dec 24, 2019 at 21:37
2
$\begingroup$

Running time depends on the model of computation. For example, the problem "Given strings $s$ and $t$, are they identical?" takes 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.

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 $n\ln(n)$ lower bound...

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I wouldn't mind multitape Turing machine, or even the RAM model. The sorting lower bound isn't really a time complexity lower bound. It's a decision tree complexity lower bound. $\endgroup$
    – Rune
    Commented Nov 11, 2009 at 1:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .