You are here: irt.org | FOLDOC | 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
FOLDOC, Topics, A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, ?, ALL