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

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

<p>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))$".</p>

<p>Is this currently a known fact?</p>

<p>Your answers will be greatly appreciated!</p>

<p>Thanks,
Avi Tal</p>

CC BY-SA 4.0
2018-05-17T17:26:36.753Z
Take a look at Theorem 1.9 from "Improving exhaustive search implies superpolynomial lower bounds": https://dl.acm.org/citation.cfm?doid=1806689.1806723
Michael Wehar
CC BY-SA 4.0
2018-05-17T18:22:52.697Z
The preprint is http://people.csail.mit.edu/rrw/improved-algs-lbs2.pdf
András Salamon
CC BY-SA 4.0
2018-05-17T19:39:40.347Z
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
CC BY-SA 4.0
2018-05-18T16:48:49.300Z
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
CC BY-SA 4.0
2018-05-18T16:49:26.097Z
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
<complexity-classes>
Are there languages in $DTIME(2^{t(n)})$ that are not in $NTIME(t(n))$?
Avi Tal
# Are there languages in $DTIME(2^{t(n)})$ that are not in $NTIME(t(n))$?

(Asked by: username_0 on 2018-05-17)

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?

Your answers will be greatly appreciated!

Thanks,
Avi Tal

**Tags:** complexity-classes
> **Comments:**
> **username_1**: Take a look at Theorem 1.9 from "Improving exhaustive search implies superpolynomial lower bounds": https://dl.acm.org/citation.cfm?doid=1806689.1806723  
> **username_2**: The preprint is http://people.csail.mit.edu/rrw/improved-algs-lbs2.pdf  
> **username_1**: 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$.  
> **username_1**: 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.  
> **username_1**: 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.  

---

## 0 answers

