Skip to main content
Computer Science

Return to Question

added 4 characters in body; edited title
Source Link
Albert Hendriks
Albert Hendriks
  • 2.5k
  • 15
  • 35

P decision problem that potentially requires at least $O$\Omega(n \log n)$ in the Turing model?

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.

P decision problem that potentially requires at least $O(n \log n)$ in the Turing model?

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 it probably requires more than $O(n \log n)$ in the Turing machine model.

P decision problem that potentially requires at least $\Omega(n \log n)$ in the Turing model?

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.

Source Link
Albert Hendriks
Albert Hendriks
  • 2.5k
  • 15
  • 35

P decision problem that potentially requires at least $O(n \log n)$ in the Turing model?

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 it probably requires more than $O(n \log n)$ in the Turing machine model.