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)