1
$\begingroup$

Currently, it is not proven that $NP \geq O(n \log n)$ in the Turing Machine Model.

The weakness of this statement can be illustrated by NP-complete problems, which we think require way more time. But I'm looking for the easiest-to-solve decision problem in P that probably has $\Omega (n \log n)$ as lower bound in the Turing machine model (I say "probably", because proving it would be a scientific breakthrough). Such a problem would best illustrate the power of the statement "$NP \geq O(n \log n)$".

It inspired me to ask about a candidate: Deterministic linear time algorithm to check if one array is a sorted version of the other, but it may not be the simplest because Yuval pointed out it probably requires more than $O(n \log n)$ in the Turing machine model.

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ What do you mean by "$NP\geq O(n\log n)$"? We certainly know that $\mathrm{DTIME}[O(n\log n)]\subsetneq \mathrm{P}\subseteq \mathrm{NP}$ (the strict inclusion is by the time hierarchy theorem). $\endgroup$
    – David Richerby
    Commented Jun 25, 2017 at 8:46
  • $\begingroup$ @DavidRicherby I'm confused. your statement seems to contradict this answer: mathoverflow.net/a/9081 $\endgroup$
    – Albert Hendriks
    Commented Jun 25, 2017 at 8:53
  • 1
    $\begingroup$ @AlbertHendriks The Math Overflow question is asking for natural problems in $\mathrm{NP}$ that cannot be solved deterministically in linear time. As that question notes, the problems that arise in the proof of the time hierarchy theorem aren't natural. (And you've still not explained what you mean by "$NP\geq O(n\log n)$".) $\endgroup$
    – David Richerby
    Commented Jun 25, 2017 at 19:46
  • $\begingroup$ In other words, you are looking for a problem whose (conjectured) time complexity should be $\Theta(n\log n)$ in the multi-tape Turing machine model. $\endgroup$
    – Yuval Filmus
    Commented Jun 25, 2017 at 21:23
  • $\begingroup$ Is your statement equal to the "deterministic machine is at least logarithmically times slower than non-deterministic" or I understood you wrong? $\endgroup$
    – rus9384
    Commented Jun 26, 2017 at 0:33

1 Answer 1

Reset to default
2
$\begingroup$

We know that there exists some problem in $P$ that can't be solved in $O(n \log n)$ time on a Turing machine; this follows from the time hierarchy theorem. As a result, there definitely exists some problem in $NP$ that can't be solved in $O(n \log n)$ time on a Turing machine. So your "it is not proven that..." statement is wrong; that is proven.

Model of Computation

When dealing with relatively "small" running times, like $O(n \log n)$, the model of computation can make a big difference. For instance, there might be problems that are solvable in $O(n \log n)$ time on a multitape Turing machine but not on a single-tape Turing machine. Also, some researchers have studied problems that can be solved by circuits.

For circuits, the situation is rather depressing. We cannot identify any computable function $f:\{0,1\}^n \to \{0,1\}$ where we have a lower bound on circuit complexity that is $\omega(n)$. We know there exist problems that can't be solved by any circuit of size $O(n)$, but we can't identify any specific problem where we can prove this is the case. See, e.g., https://cstheory.stackexchange.com/q/21400/5038. This illustrates just how hard it is to prove lower bounds (see, e.g., https://cstheory.stackexchange.com/q/17789/5038 and references therein).

Plausible candidates

Nonetheless, there are many plausible candidates where it might not be possible to solve them in $O(n \log n)$ time. For instance, 3SUM and other similar problems don't appear to have any $O(n \log n)$-time algorithm that we can find, so they might be reasonable candidates. Other examples include all-pairs shortest paths and linear programming.

For more, see https://cstheory.stackexchange.com/q/1284/5038 and https://cstheory.stackexchange.com/q/17578/5038.

Careful with those Omegas!

You wrote that you wanted to find a problem that can't be solved in $O(n \log n)$ time. You also wrote that you wanted to find a problem that takes $\Omega(n \log n)$ time to solve. Beware that those aren't the same thing. The former is equivalent to looking for a problem that takes $\omega(n \log n)$ time to solve.

It is known that any language (decision problem) that can be solved in $o(n \log n)$ time on a single-tape Turing machine is in fact a regular language. Thus if you take any language that is not regular but is in $P$, it follows that the running time for a Turing machine to decide it is $\Omega(n \log n)$. Beware that this might not be what you want: this means the running time might be $\Theta(n \log n)$ or it might be even larger. I suspect you meant to ask for a problem that cannot be solved in $O(n \log n)$ time, i.e., that requires $\omega(n \log n)$ time.

Improve this answer
$\endgroup$
3
  • $\begingroup$ The proof of the time hierarchy theorem is constructive, and you can extract a problem which requires more than $n\log n$ time. It just isn't so natural. $\endgroup$
    – Yuval Filmus
    Commented Jun 26, 2017 at 0:44
  • $\begingroup$ @YuvalFilmus, OK, thanks for explaining and for the correction -- I misunderstood the time hierarchy theorem. $\endgroup$
    – D.W. ♦
    Commented Jun 26, 2017 at 5:07
  • $\begingroup$ I was under the impression that the best-known lower bound for NP problems was O(n) or slightly above. I was wrong. So I was actually looking for a decision problem that can be solved in O(n log n) but not in O(n). $\endgroup$
    – Albert Hendriks
    Commented Jun 26, 2017 at 12:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.