# NTIME(n^k) ≠ DTIME(n^k) ?

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?

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.)
$$\mathsf{DTIME}\left( n \sqrt{log^*(n)}\right) \neq \mathsf{NTIME}\left(n \sqrt{log^*(n)}\right)$$