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 decisionproblems in a number of steps that is a polynomial function

of the size of the input

(1995-04-27)