Nondeterministic Turing Machine
<complexity> 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
(1995-04-27)
Nearby terms:
nondeterministic « nondeterministic automaton «
nondeterministic polynomial time « Nondeterministic
Turing Machine » non-impact printer » non-interlaced »
nonintrusive testing
