|
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)
|
