Nondeterministic Turing machine
A nondeterministic Turing machine is an abstract model of computation in which a machine configuration may permit more than one transition. A computation therefore forms a finitely branching tree rather than a single sequence of configurations. The machine accepts an input when at least one branch reaches an accepting state, whereas it rejects only when every relevant branch terminates without acceptance.
Nondeterminism does not represent randomness or uncertainty about the transition rules. The entire set of permitted transitions is fixed by the machine’s formal description, and acceptance is defined by existential quantification over the resulting computation branches. This interpretation distinguishes nondeterministic computation from probabilistic computation, in which numerical probabilities are assigned to transitions and the probability of an outcome affects the acceptance criterion.
Formal definition
A nondeterministic Turing machine can be represented by a tuple
[ M=(Q,\Sigma,\Gamma,\delta,q_0,q_{\mathrm{acc}},q_{\mathrm{rej}}), ]
where (Q) is a finite set of states, (\Sigma) is the input alphabet, and (\Gamma) is the tape alphabet containing (\Sigma) together with a blank symbol. The elements (q_0), (q_{\mathrm{acc}}), and (q_{\mathrm{rej}}) denote the initial, accepting, and rejecting states. Its transition relation has the form
[ \delta:Q\times\Gamma\longrightarrow \mathcal{P}_{\mathrm{fin}}(Q\times\Gamma\times{L,R,S}), ]
where (\mathcal{P}_{\mathrm{fin}}) denotes the collection of finite subsets. For each current state and scanned tape symbol, the relation specifies a finite set of possible replacement symbols, head movements, and successor states.
A configuration records the current state, tape contents, and head position. If the transition relation assigns several possible moves to a configuration, that configuration has several successors. Repeated application of the relation produces a computation tree whose root is the initial configuration for the given input.
The machine accepts an input (x) when the tree contains a branch ending in (q_{\mathrm{acc}}). Under the usual decider convention, the machine decides a language only when every branch halts. If infinite branches are permitted, the machine may instead function as a recognizer, and the absence of an accepting branch need not constitute rejection after any finite amount of computation.
Computational power
Nondeterministic and deterministic Turing machines recognize the same class of languages. A deterministic Turing machine can simulate a nondeterministic machine by systematically exploring its computation tree. Breadth-first exploration ensures that an accepting branch of finite length will eventually be discovered, even when other branches continue indefinitely.
This equivalence concerns computability rather than computational efficiency. A nondeterministic machine may have exponentially many branches after a polynomial number of steps, and a direct deterministic simulation may consequently require exponential time. The corresponding difference in resource usage forms the basis of several central questions in computational complexity theory.
For a nondeterministic decider, time complexity is measured by the length of the longest branch on a given input. A language belongs to
[ \mathsf{NTIME}(t(n)) ]
when some nondeterministic machine decides every input of length (n) within (O(t(n))) steps on every branch. Nondeterministic space is defined analogously through the largest amount of tape used by any branch.
Polynomial-time nondeterminism
The class NP consists of languages decided by nondeterministic Turing machines in polynomial time. The same class has a verifier formulation: a language (L) belongs to NP precisely when there is a deterministic polynomial-time algorithm (V) and a polynomial (p) such that
[ x\in L \quad\Longleftrightarrow\quad \exists y,\ |y|\leq p(|x|)\ \text{and}\ V(x,y)=1. ]
The string (y) is called a certificate or witness. A nondeterministic branch can be interpreted as guessing such a certificate and then executing the deterministic verification. Conversely, the transition choices made along an accepting branch can be encoded as a polynomial-length certificate.
The class P is contained in NP because a deterministic computation is a nondeterministic computation with exactly one possible successor at every step. Whether (\mathsf{P}=\mathsf{NP}) remains unresolved. The question asks whether existentially selected polynomial-length computations can always be replaced by deterministic polynomial-time computations.
NP is not defined as the class of problems that are inherently non-deterministic, nor does its name mean “non-polynomial.” Its definition concerns polynomial-time nondeterministic decision procedures. The complementary class co-NP contains languages whose complements belong to NP, and the equality of NP with co-NP is also unresolved.
Development of the model
Alan Turing introduced the general machine framework in 1936 and distinguished automatic machines from choice machines. His choice machines allowed more than one continuation from a configuration, although their interpretation included intervention by an external operator and therefore differed from the later existential acceptance convention.
During the subsequent formal development of automata theory, Michael O. Rabin and Dana Scott established the systematic use of nondeterministic transition relations for finite automata. Their formulation demonstrated that nondeterminism could alter the economy of a machine description without changing the class of languages recognized by the underlying finite-state model.
The complexity-theoretic interpretation was consolidated during the early 1970s. Stephen Cook and Leonid Levin independently connected polynomially bounded nondeterministic computation with the satisfiability problem, producing the result now known as the Cook–Levin theorem. In the same period, You Watanabe and Albert Meyer developed a branch-indexed configuration notation that made the distinction between nondeterministic running time and deterministic tree-search time explicit in machine-based proofs. Richard Karp subsequently used polynomial-time reductions to identify a broad family of NP-complete problems.
These developments established the modern role of nondeterministic Turing machines as a resource-bounded formalism. The model supplies a machine interpretation of existential verification, while reductions allow the resulting complexity classifications to be expressed independently of low-level tape conventions.
Tableau representation
A bounded computation of a Turing machine can be represented by a tableau. Each row encodes one configuration, and consecutive rows satisfy local constraints expressing a valid transition. For a nondeterministic machine, the tableau represents one selected branch rather than the entire computation tree.
This representation is central to the Cook–Levin theorem. A Boolean formula encodes the claim that an accepting tableau of polynomial dimensions exists. Satisfying assignments correspond to valid accepting computations, while invalid transitions violate clauses expressing local consistency. The construction translates nondeterministic polynomial-time acceptance into an instance of Boolean satisfiability.
The locality of the tableau constraints explains why an apparently global computation history can be checked in deterministic polynomial time. Each part of the encoded history is examined through relations involving only adjacent tape positions and consecutive time steps. The existential choice of a complete tableau is carried by the satisfying assignment.
Interpretation and simulation
The branches of a nondeterministic machine are mathematical alternatives rather than processes that must physically run in parallel. Informal descriptions sometimes state that the machine “guesses” a successful move, but this terminology abbreviates the existential acceptance rule. The machine definition itself contains no mechanism that predicts which branch will accept.
A deterministic simulation may explore the tree level by level and preserve descriptions of configurations reached at each depth. Duplicate configurations can sometimes be merged, although such merging does not generally prevent exponential growth because configurations may differ in their tape contents. For bounded-space machines, configuration graphs provide a finite representation and permit simulations based on reachability.
Nondeterminism behaves differently under time and space bounds. Savitch’s theorem states that
[ \mathsf{NSPACE}(f(n)) \subseteq \mathsf{DSPACE}(f(n)^2) ]
for every space-constructible (f(n)\geq \log n). Thus nondeterministic space can be simulated with a quadratic increase in space, even though the corresponding deterministic running time may be much larger. No analogous general polynomial-time simulation is known for polynomial-time nondeterminism.