Nondeterministic Turing Machine
A normal (deterministic) Turing Machine that has a "guessing head" - a write-only head that writes a guess at a solution on the tape first, based on some arbitrary internal algorithm. The regular Turing Machine then runs and returns "yes" or "no" to indicate whether the solution is correct.A nondeterministic Turing Machine can solve nondeterministic polynomial time computational decision problems in a number of steps that is a polynomial function of the size of the input
Last updated: 1995-04-27
nondeterministic polynomial time ♦ Nondeterministic Turing Machine ♦ non-impact printer
Try this search on Wikipedia, Wiktionary, Google, OneLook.