Nondeterministic Turing machine

Summary

A nondeterministic Turing machine is a Turing machine that may have several possible moves in a given situation. It accepts an input when at least one of its possible runs reaches an accepting state. It recognises the same languages as a deterministic machine, but its time cost can be much smaller. The class NP consists of the problems that such a machine decides in polynomial time, which makes it central to the P versus NP question.