Skip to main content
1 of 2
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)$ ?

Daniel
  • 191
  • 8