Skip to main content
2 of 2
deleted 227 characters in body
D.W.
  • 165.6k
  • 21
  • 230
  • 490

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.

D.W.
  • 165.6k
  • 21
  • 230
  • 490