If a non-deterministic Turing machine can just "guess" the correct answer to a problem, does it do this in constant time/immediately? Also, does this also apply to problems in NP too?


A nondeterministic Turing machine can guess at most one bit each step — this is how they are defined. In particular, a nondeterministic Turing machine running in constant time can be converted to a deterministic machine also running in constant time. This should allow you to answer your own question.

  • $\begingroup$ Yep, so this would mean that given a problem in EXP, it would need exponential time to solve it also. The only guarantee, is that it will get the solution, if there is one. Maybe this means that a a NTM, is a generalisation of a DTM? $\endgroup$ – WeCanBeFriends Jun 20 '19 at 11:29
  • $\begingroup$ Why is it Non-Deterministic, when we know that if a solution exists, then it will produce true, but if a solution does not exist then it will produce false. Unlike PPT, where we can get false negatives for example? $\endgroup$ – WeCanBeFriends Jun 20 '19 at 11:31
  • $\begingroup$ When we say a NTM "guesses" are we talking about it, making "lucky coin flips" like in a PPT, if so why does the definition not include the max coin flips? $\endgroup$ – WeCanBeFriends Jun 20 '19 at 11:39
  • $\begingroup$ Nondeterministic Turing machines indeed generalize deterministic ones. They have the additional power of guessing. Each guess costs one time step, so we are taking into account the maximum number of guesses (it's part of the running time). $\endgroup$ – Yuval Filmus Jun 20 '19 at 13:07

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.