Non Deterministic Turing Machine

A variation on the TuringMachine that picks all possible alternatives at each decision point. Used as the basis for ComplexityTheory?. Is not more powerful than a deterministic TuringMachine--i.e. all problems which are decideable on a DTM are also decideable on a NDTM--but NDTMs can solve many problems faster. The classical example of this is the class of problems known as NP--this means "nondeterministic polynomial"; such problems can be solved in polynomial time on an NDTM, but it is not known whether or not they can be solved in polynomial time on a deterministic TuringMachine (see NpComplete).

See NonDeterministic