33
$\begingroup$

In "On determinism versus nondeterminism and related problems" (Proc. IEEE FOCS, pages 429–438, 1983), Paul, Pippenger, Szemerédi and Trotter proved that
$\mathsf{NTIME}(n)\neq\mathsf{DTIME}(n)$.

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

$\endgroup$
26
$\begingroup$

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.)

$\endgroup$
11
$\begingroup$

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=10.1.1.22.2392

$\endgroup$
  • 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$ – András Salamon Feb 7 '13 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 Feb 7 '13 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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