In "On determinism versus nondeterminism and related problems" (Proc. IEEE FOCS, pages 429–438, 1983), Paul, Pippenger, Szemerédi and Trotter proved that

This answers my question with k=1. Is anything known about a similar result for another fixed k?


2 Answers 2


No unconditional lower bound is known for any $k \geq 2$ in the multitape TM model (or any model stronger than it).

Ravi Kannan studied this problem in "Towards separating nondeterminism from determinism" (1984). In the process of trying to show $NTIME(n^k) \neq TIME(n^k)$ he managed to prove the following: there is some universal constant $c \geq 1$ such that for every $k$, $NTIME(n^k) \not \subseteq TIME-SPACE(n^k,n^{k/c})$. Here, $TIME-SPACE(n^k, n^{k/c})$ is the class of languages recognized by machines using time $n^k$ and space $n^{k/c}$ simultaneously. Clearly $TIME-SPACE(n^k,n^{k/c}) \subseteq TIME(n^k)$ but it is not known whether they are equal.

If you assume for some $k \geq 2$ that $NTIME(n^k) = TIME(n^k)$, you get interesting consequences. $P=NP$ is obvious, but it also implies that ${\sf NL} \neq {\sf P}$. This can be proved using an "alternation-trading" argument. Basically, for every $k$ and every language $L \in {\sf NL}$, there is a constant $c$ and some alternating machine that recognizes $L$ and makes $c$ alternations, guesses $O(n)$ bits per alternation, then switches to a deterministic mode and runs in $n^k$ time. (This follows, for example, from playing around with the constructions in Fortnow, "Time-Space Tradeoffs for Satisfiability" (1997).) Now if $TIME(n^k) = NTIME(n^k)$ then all these $c$ alternations can be removed with only a small amount of overhead, and you end up with a $TIME(n^k)$ computation that recognizes $L$. Hence ${\sf NL }\subseteq TIME(n^k) \neq {\sf P}$. Probably no such alternating simulation exists, but if you can rule it out, then you'll have the lower bound you seek. (Note: I believe that the above argument is also in Kannan's paper.)


while not exactly what you are asking, rj lipton comments in his blog on the foundational difficulty of results in this area and that the typical approach of "padding" does not apply [1] & points out that the PPST result as you cite has recently been slightly extended (by a logarithmic factor) by Santhanam [2] ie

$$ \mathsf{DTIME}\left( n \sqrt{log^*(n)}\right) \neq \mathsf{NTIME}\left(n \sqrt{log^*(n)}\right) $$

[1] http://rjlipton.wordpress.com/2011/01/19/we-believe-a-lot-but-can-prove-little/

[2] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=

  • 1
    $\begingroup$ The official version of Rahul Santhanam's 2001 paper is dx.doi.org/10.1109/CCC.2001.933895 (and is hardly recent). $\endgroup$ Commented Feb 7, 2013 at 16:13
  • $\begingroup$ Lipton used the phrase "more recently" in his blog citing it. its "more recent" to the PPST 1983 result. $\endgroup$
    – vzn
    Commented Feb 7, 2013 at 16:27

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.