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
| < Previous Terms | Terms Containing Nondeterministic Turing Machine | Next Terms > |
| non-algorithmic procedure nondeterminism nondeterministic nondeterministic automaton nondeterministic polynomial time | nondeterministic automaton nondeterministic polynomial time Nondeterministic Turing Machine | non-impact printer non-interlaced nonintrusive testing nonlinear Non-Maintainer Upload |
