Skip to main content
Computer Science

Return to Question

added 16 characters in body
Source Link
Daniel
Daniel
  • 191
  • 8

There is a theorem that said for every nondeterministicnondeterministic Turing machine that runs in $O(n^k)$ there is an equivalent deterministicdeterministic 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 deterministicdeterministic Turing machine that runs in $O(2^{n^k})$ we can't construct nondeterministicnondeterministic Turing machine that runs in $O(n^k)$ ?

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)$ ?

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)$ ?

Source Link
Daniel
Daniel
  • 191
  • 8

Why $TIME(2^{n^k})\nsubseteq NTIME(n^k)$?

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)$ ?