<p>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] &amp; points out that the PPST result as you cite has recently been slightly extended (by a logarithmic factor) by Santhanam [2] ie </p>

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

<p>[1] <a href="http://rjlipton.wordpress.com/2011/01/19/we-believe-a-lot-but-can-prove-little/">http://rjlipton.wordpress.com/2011/01/19/we-believe-a-lot-but-can-prove-little/</a></p>

<p>[2] <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.2392">http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.2392</a></p>

CC BY-SA 3.0
2013-02-07T16:13:29.657Z
The official version of Rahul Santhanam's 2001 paper is http://dx.doi.org/10.1109/CCC.2001.933895 (and is hardly recent).
András Salamon
CC BY-SA 3.0
2013-02-07T16:27:59.643Z
Lipton used the phrase "more recently" in his blog citing it. its "more recent" to the PPST 1983 result.
vzn
CC BY-SA 3.0
2012-01-09T19:32:05.797Z
2012-01-09T19:32:05.797Z
vzn
<p>No unconditional lower bound is known for any <span class="math-container">$k \geq 2$</span> in the multitape TM model (or any model stronger than it).</p>
<p>Ravi Kannan studied this problem in <a href="https://doi.org/10.1007/BF01744432" rel="nofollow noreferrer">&quot;Towards separating nondeterminism from determinism&quot; (1984)</a>. In the process of trying to show <span class="math-container">$NTIME(n^k) \neq TIME(n^k)$</span> he managed to prove the following: there is some universal constant <span class="math-container">$c \geq 1$</span> such that for every <span class="math-container">$k$</span>, <span class="math-container">$NTIME(n^k) \not \subseteq TIME-SPACE(n^k,n^{k/c})$</span>. Here, <span class="math-container">$TIME-SPACE(n^k, n^{k/c})$</span> is the class of languages recognized by machines using time <span class="math-container">$n^k$</span> and space <span class="math-container">$n^{k/c}$</span> simultaneously. Clearly <span class="math-container">$TIME-SPACE(n^k,n^{k/c}) \subseteq TIME(n^k)$</span> but it is not known whether they are equal.</p>
<p>If you assume for some <span class="math-container">$k \geq 2$</span> that <span class="math-container">$NTIME(n^k) = TIME(n^k)$</span>, you get interesting consequences. <span class="math-container">$P=NP$</span> is obvious, but it also implies that <span class="math-container">${\sf NL} \neq {\sf P}$</span>. This can be proved using an &quot;alternation-trading&quot; argument. Basically, for every <span class="math-container">$k$</span> and every language <span class="math-container">$L \in {\sf NL}$</span>, there is a constant <span class="math-container">$c$</span> and some alternating machine that recognizes <span class="math-container">$L$</span> and makes <span class="math-container">$c$</span> alternations, guesses <span class="math-container">$O(n)$</span> bits per alternation, then switches to a deterministic mode and runs in <span class="math-container">$n^k$</span> time. (This follows, for example, from playing around with the constructions in <a href="http://people.cs.uchicago.edu/%7Efortnow/papers/npvsnl.pdf" rel="nofollow noreferrer">Fortnow, &quot;Time-Space Tradeoffs for Satisfiability&quot; (1997)</a>.) Now if <span class="math-container">$TIME(n^k) = NTIME(n^k)$</span> then all these <span class="math-container">$c$</span> alternations can be removed with only a small amount of overhead, and you end up with a <span class="math-container">$TIME(n^k)$</span> computation that recognizes <span class="math-container">$L$</span>. Hence <span class="math-container">${\sf NL }\subseteq TIME(n^k) \neq {\sf P}$</span>. 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.)</p>

CC BY-SA 4.0
2010-09-08T17:41:03.517Z
2022-10-05T09:45:29.837Z
2022-10-05T09:45:29.837Z
Ryan Williams
<p>In "On determinism versus nondeterminism and related problems" (Proc. IEEE FOCS, pages 429–438, 1983), Paul, Pippenger, Szemerédi and Trotter proved that<br>
$\mathsf{NTIME}(n)\neq\mathsf{DTIME}(n)$.</p>

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

<cc.complexity-theory>
NTIME(n^k) ≠ DTIME(n^k) ?
Bruno
# NTIME(n^k) ≠ DTIME(n^k) ?

(Asked by: username_0 on 2010-09-08)

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?

**Tags:** cc.complexity-theory


---

## 2 answers

### Answer by username_3 on 2010-09-08. Score: 28 | Accepted answer

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)](https://doi.org/10.1007/BF01744432). 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)](http://people.cs.uchicago.edu/%7Efortnow/papers/npvsnl.pdf).) 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.)


---

### Answer by username_1 on 2012-01-09. Score: 11

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>

> **Comments:**
> **username_2**: The official version of Rahul Santhanam's 2001 paper is http://dx.doi.org/10.1109/CCC.2001.933895 (and is hardly recent).  
> **username_1**: Lipton used the phrase "more recently" in his blog citing it. its "more recent" to the PPST 1983 result.  

---

