In computational complexity theory, an alternating Turing machine (ATM) is a non-deterministic Turing machine (NTM) with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP.
The concept of an ATM was set forth by Chandra and Stockmeyer[1] and independently by Kozen[2] in 1976, with a joint journal publication in 1981.
[3] The definition of NP uses the existential mode of computation: if any choice leads to an accepting state, then the whole computation accepts.
The definition of co-NP uses the universal mode of computation: only if all choices lead to an accepting state does the whole computation accept.
(Thus a universal state with no transitions accepts unconditionally; an existential state with no transitions rejects unconditionally).
Formally, a (one-tape) alternating Turing machine is a 5-tuple
is said to be accepting if all configurations reachable in one step are accepting, and rejecting if some configuration reachable in one step is rejecting.
is said to be accepting when there exists some configuration reachable in one step that is accepting and rejecting when all configurations reachable in one step are rejecting (this is the type of all states in a classical NTM except the final state).
M is said to accept an input string w if the initial configuration of M (the state of M is
, the head is at the left end of the tape, and the tape contains w) is accepting, and to reject if the initial configuration is rejecting.
Note that it is impossible for a configuration to be both accepting and rejecting, however, some configurations may be neither accepting or rejecting, due to the possibility of nonterminating computations.
An ATM decides a formal language in time
steps is sufficient to label the initial configuration as accepting or rejecting.
if examining configurations that do not modify tape cells beyond the
Perhaps the most natural problem for alternating machines to solve is the quantified Boolean formula problem, which is a generalization of the Boolean satisfiability problem in which each variable can be bound by either an existential or a universal quantifier.
The alternating machine branches existentially to try all possible values of an existentially quantified variable and universally to try all possible values of a universally quantified variable, in the left-to-right order in which they are bound.
After deciding a value for all quantified variables, the machine accepts if the resulting Boolean formula evaluates to true, and rejects if it evaluates to false.
Thus at an existentially quantified variable the machine is accepting if a value can be substituted for the variable that renders the remaining problem satisfiable, and at a universally quantified variable the machine is accepting if any value can be substituted and the remaining problem is satisfiable.
Such a machine decides quantified Boolean formulas in time
The Boolean satisfiability problem can be viewed as the special case where all variables are existentially quantified, allowing ordinary nondeterminism, which uses only existential branching, to solve it efficiently.
The following complexity classes are useful to define for ATMs: These are similar to the definitions of P, PSPACE, and EXPTIME, considering the resources used by an ATM rather than a deterministic Turing machine.
Chandra, Kozen, and Stockmeyer[3] proved the theorems when
A more general form of these relationships is expressed by the parallel computation thesis.
(It is an alternating Turing machine whose states are divided into k sets.
by a machine beginning in an existential state and alternating at most
is defined in the same way, but beginning in a universal state; it consists of the complements of the languages in
is defined similarly for space bounded computation.
Consider the circuit minimization problem: given a circuit A computing a Boolean function f and a number n, determine if there is a circuit with at most n gates that computes the same function f. An alternating Turing machine, with one alternation, starting in an existential state, can solve this problem in polynomial time (by guessing a circuit B with at most n gates, then switching to a universal state, guessing an input, and checking that the output of B on that input matches the output of A on that input).
As a corollary of the Immerman–Szelepcsényi theorem, the logarithmic space hierarchy collapses to its first level.
An alternating Turing machine in polynomial time with k alternations, starting in an existential (respectively, universal) state can decide all the problems in the class