# Are there languages in $DTIME(2^{t(n)})$ that are not in $NTIME(t(n))$?

Are there languages in $DTIME(2^{t(n)})$ that are not in $NTIME(t(n))$?

This question came up while watching "Graduate Complexity at CMU - Lecture 2: Hierarchy Theorems (Time, Space, and Nondeterministic)" https://www.youtube.com/watch?v=HrJKTTJfweo

In time 00:53:30 - Prof. Ryan O'Donnell states that "there are languages decidable in $DTIME(2^{t(n)})$ that are undecidable in $NTIME(t(n))$".

Is this currently a known fact?

Thanks, Avi Tal

• Take a look at Theorem 1.9 from "Improving exhaustive search implies superpolynomial lower bounds": dl.acm.org/citation.cfm?doid=1806689.1806723 – Michael Wehar May 17 '18 at 17:26
• The preprint is people.csail.mit.edu/rrw/improved-algs-lbs2.pdf – András Salamon May 17 '18 at 18:22
• For any fixed number of tapes with fixed alphabets, for non-determinism where each non-deterministic guess is a binary choice, and for appropriate functions $t(n)$, we have that $NTIME(t(n)) \subseteq DTIME(2^{(1 - \delta) t(n)}) \subsetneq DTIME(2^{t(n)})$ for some $\delta > 0$. – Michael Wehar May 17 '18 at 19:39
• This follows from the paper mentioned above combined with the time hierarchy theorem. Note: By $NTIME(t(n))$, I mean that the languages can be decided by non-deterministic machines that run in $t(n)$ time, not $O(t(n))$ time. This is significant because it restricts the computation to exactly $t(n)$ non-deterministic binary guesses. – Michael Wehar May 18 '18 at 16:48
• It's not clear to me if one could generalize this result to an unrestricted number of tapes with the more standard notion of non-determinism where you can make non-binary non-deterministic guesses. – Michael Wehar May 18 '18 at 16:49

If $\mathrm{NTIME}(n) \supseteq \mathrm{DTIME}(2^{n/2000})$ (where NTIME and DTIME uses constant factor in the big-oh) then for all time-constructible $t\geq n$, we have that $\mathrm{NTIME}(t) = \mathrm{DTIME}(2^{\mathrm{O}(t)})\supsetneq \mathrm{DTIME}(2^t)$ to the contrary to your quest. So, in that case, requiring the NTM to read a tape of nondeterministic guesses are essential to separate these classes.
And it is still open that $\mathrm{NTIME}(n) = \mathrm{E}$.
Given a language $\mathrm{L}\in \mathrm{DTIME}(2^{\mathrm{O}(t)})$ decided by a TM running in time $2^{ct}$ where $c$ is some constant, construct the language $\mathrm{L}_\mathrm{pad} = \{x10^{2000*ct-1-\vert x\vert}\vert x\in \mathrm{L}\}$. Clearly, $\mathrm{L}_\mathrm{pad}$ can be decided by a TM running in time $\mathrm{DTIME}(2^{n/2000})$, i.e. $\mathrm{L}_\mathrm{pad}\in \mathrm{DTIME}(2^{n/2000})$. By our assumption, we have that $\mathrm{L}_\mathrm{pad}\in \mathrm{NTIME}(n)$, i.e. there exists an NTM deciding $\mathrm{L}_\mathrm{pad}$ in non-deterministic time $dn$ for some constant $d$. Now, we describe the NTM for $\mathrm{L}$. When given an input dtring $x$, our NTM for $\mathrm{L}$ first pads it up to length $2000*ct$ and then run the $\mathrm{NTIME}(n)$ NTM for $\mathrm{L}_{pad}$. Clearly, our NTM runs in non-deterministic time $cdt$, putting $\mathrm{L}$ inside $\mathrm{NTIME}(t)$.