0
$\begingroup$

There is a theorem that said for every nondeterministic Turing machine that runs in $O(n^k)$ there is an equivalent deterministic Turing machine that runs in $O(2^{n^k})$.

From this theorem, I understand that $NTIME(n^k)\subseteq TIME(2^{n^k})$.

Why doesn't the other direction hold?

i.e., why for every deterministic Turing machine that runs in $O(2^{n^k})$ we can't construct nondeterministic Turing machine that runs in $O(n^k)$ ?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Just to be precise, there is an equivalent deterministic machine that runs in $2^{O(n^k)}$, not necessarily $O(2^{n^k}).$ $\endgroup$
    – spaceisdarkgreen
    Commented 11 hours ago

1 Answer 1

Reset to default
1
$\begingroup$

If $\mathsf{TIME}(2^{n^k})\subseteq \mathsf{NTIME}(n^k)$, that would mean that $\mathsf{EXP} = \mathsf{NP}$, which is an open problem.

I don't think that means that this inclusion doesn't hold, just that we don't know the answer.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Hello Nathaniel! Do you have any intuition to why exponential deterministic TM can't be translated consistently to polynomial non-deterministic polynomial TM? I understand the part of $EXP=NP$ but there are miracles thing that associated with nondeterminism (from the equivalents of DFA and NFA, and the translation of polynomial nondeterministic TM to exponential deterministic TM) that made me believe maybe there is a translation like this and I just don't see it. $\endgroup$
    – Daniel
    Commented 15 hours ago
  • $\begingroup$ @Daniel Using non-determinism to do an exponential amount of stuff in polynomial time seems dependent on the ability to "parallelize" that stuff. $\endgroup$
    – spaceisdarkgreen
    Commented 11 hours ago
  • 1
    $\begingroup$ @Daniel also “a miracle could happen and I just don’t see it” is a pretty good summary of many open questions in complexity theory. $\endgroup$
    – spaceisdarkgreen
    Commented 10 hours ago
  • $\begingroup$ @spaceisdarkgreen Can you elaborate on "the ability to parallelize that stuff" ? $\endgroup$
    – Daniel
    Commented 4 hours ago

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.