Suppose I assume that the complexity of a non-deterministic Turing machine $N$ is $T(n)$, $n$ is the length of the input string. What would be the time complexity of a deterministic Turing machine $D$ equivalent to $N$?

  • 1
    $\begingroup$ That depends on $N$. For the worst case, you might want to check e.g. the Exponential Time Hypothesis. There is not a strong theorem like Savitch's Teorem for space complexity, establishing a similar tight connection. $\endgroup$ – ttnick Apr 16 at 17:42
  • $\begingroup$ How do you construct $D$ from $N$? $\endgroup$ – Yuval Filmus Apr 19 at 5:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.