So we know a nondeterministic Turing machine (NTM) is just a theoretical model of computation. They are used in thought experiments to examine the abilities and limitations of computers. Commonly used to dicuss P vs NP, and how NP problems cannot be solved in polynomial time UNLESS the computation was done on the hypothetical NTM. We also know an NTM would use a set of rules to prescribe more than one action to be performed for any given situation. In other words, attempt many different options simultaneously.

Isn't this what distributed computing does across commodity hardware? Run many different possible calculations in parallel? And the GPU, does this within a single machine. Why isn't this considered an NTM?


In parallel computing, the threads can talk to each other and exchange information during the computation. In nondeterminism, the only "communication" between threads is that we compute the OR of all possible computation paths. This is much more limited.

If you simulate nondeterminism by spawning parallel computations for every nondeterministic choice, you need an exponential number of threads for a polynomial time computation. We know how to build parallel machines in the real world, we don't know how to build nondeterministic ones.

  • $\begingroup$ This was my suspicion. It is currently not feasible to construct a physical machine that could try all possible combinations / paths in order to brute force the calculation in polynomial time. Thank you. $\endgroup$ – Cybernetic Jan 7 '20 at 1:44

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.