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

  • 3
    $\begingroup$ Take a look at Theorem 1.9 from "Improving exhaustive search implies superpolynomial lower bounds": dl.acm.org/citation.cfm?doid=1806689.1806723 $\endgroup$ – Michael Wehar May 17 '18 at 17:26
  • 1
    $\begingroup$ The preprint is people.csail.mit.edu/rrw/improved-algs-lbs2.pdf $\endgroup$ – András Salamon May 17 '18 at 18:22
  • 2
    $\begingroup$ 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$. $\endgroup$ – Michael Wehar May 17 '18 at 19:39
  • $\begingroup$ 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. $\endgroup$ – Michael Wehar May 18 '18 at 16:48
  • 1
    $\begingroup$ 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. $\endgroup$ – 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)$.

  • 1
    $\begingroup$ Hi Matt, Can you show why NTIME(t)=DTIME(2^O(t)) ? Thanks $\endgroup$ – Avi Tal Sep 12 '18 at 17:44

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.