Alternating Turing machine
|
|
In computational complexity theory, an alternating Turing machine is a non-deterministic Turing machine with a rule for accepting computations that generalizes the rules used in the definition of the complexity classes NP and co-NP.
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: if all choices lead to an accepting state, then the whole computation accepts. An alternating Turing machine (or to be more precise, the definition of acceptance for such a machine) alternates between these modes.
An alternating Turing machine is a non-deterministic Turing machine whose states are divided into two sets: existential states and universal states. An existential state is accepting if some transition leads to an accepting state; a universal state is accepting if every transition leads to an accepting state. (Thus a universal state with no transitions accepts unconditionally; an existential state with no transitions rejects unconditionally). The machine as a whole accepts if the initial state is accepting.
Perhaps the simplest 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 for the existential variables and universally for the universal variables, in the left-to-right order in which they are bound. The boolean satisfiability problem can be viewed as the special case where all variables are existential, allowing ordinary nondeterminism, which uses only existential branching, to solve it efficiently.
An alternating Turing machine with k alternations is an alternating Turing machine which switches from an existential to a universal state or vice versa no more than k-1 times. (It is an alternating Turing machine whose states are divided into k sets. The states in even-numbered sets are universal and the states in odd-numbered sets are existential (or vice versa). The machine has no transitions between a state in set i and a state in set j < i.)
For example, 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 states, 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).
An alternating Turing machine, with k alternations, starting in an existential (respectively, universal) state can decide all the problems in the class <math>\Sigma_k\rm{P}<math> (respectively, <math>\Pi_k\rm{P}<math>) in polynomial time. See the polynomial hierarchy article.
An alternating Turing machine with unlimited alternations can decide all the problems in the class PSPACE in polynomial time.