I'm studying Turing machines and I came across the following definitions:

NP is the set of problems that can be solved in polynomial time by a non-deterministic Turing machine.


Let t(n) be a function, where t(n) ≥ n. Then every t(n) time non-deterministic single-tape Turing machine has an equivalent 2^O(t(n)) time deterministic single-tape TM.

From what I understand, the second theorem is closely related to the P = NP problem.

My question is:

Why does it actually matter so much whether we can convert a non-deterministic TM running in polynomial time to a deterministic TM running in polynomial time? What are the 'advantages' of a deterministic TM over the non-deterministic one?


1 Answer 1


What are the 'advantages' of a deterministic TM over the non-deterministic one?

The advantage of the deterministic TM is that deterministic Turing Machines represent the type of computation we are capable of, whether by hand, calculator or computer. The non-deterministic Turing Machine includes a power our intuitive computation does not have – the power to branch out its computation indefinitely (often also conceptualized as "the ability to make lucky guesses").

At any point of its computation, a NTM can choose to perform two (or more) different actions at the same time. This results in more than one "parallel copies" of the same Turing Machine existing, at different states. These parallel copies of the machine can spawn further parallel copies in a tree-like multiverse. The execution of all of these parallel copies is halted whenever any of them accepts the input string, or all of them have rejected it.

As an example of how this can be applied to solve an actual problem, consider a NTM solving a SAT problem. A NTM can simply read the logical statement and assign both true and false values to each variable in a separate branch. Finally, every branch can simply read their version of the statement and accept if they ended up with a satisfied one, reject otherwise.

Sadly, not having access to NTM, we cannot solve problems as simply – our deterministic tools cannot spring forth infinite universe to try solving the instance in, and can at best emulate non-deterministic models one branch of the tree at a time. If we had access to an NTM, it would be a superior model, but such machines are unlikely to be possible in our world. Hence statements about deterministic Turing Machines are likely to be of much more practical interest than those about non-deterministic ones.

  • $\begingroup$ Based on what you wrote, is it reasonable to say that NTMs are kind of like computers with an infinite number of threads? $\endgroup$ Commented Jun 22, 2022 at 14:27
  • $\begingroup$ @confused An unbounded number of threads is one way to look at it, yes – though they lack shared memory, but they get the perfect communication (for the case of acceptance) in compensation. $\endgroup$
    – kviiri
    Commented Jun 23, 2022 at 5:58

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.