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. An alternating Turing 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.. The machine as a whole accepts if the initial state is accepting.
Formal definition
Formally, a alternating Turing machine is a 5-tuple where
If M is in a state with then that configuration is said to be accepting, and if the configuration is said to be rejecting. A configuration with 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. A configuration with is said to be accepting when there exists some configuration reachable in one step which is accepting and rejecting when all configurations reachable in one step are rejecting. M is said to accept an input string w if the initial configuration of M is accepting, and to reject if the initial configuration is rejecting.
Resource bounds
When deciding if a configuration of an ATM is accepting or rejecting using the above definition, it is not necessary to examine all configurations reachable from the current configuration. In particular, an existential configuration can be labelled as accepting if any successor configuration is found to be accepting, and a universal configuration can be labelled as rejecting if any successor configuration is found to be rejecting. An ATM decides a formal language in time if, on any input of length, examining configurations only up to steps is sufficient to label the initial configuration as accepting or rejecting. An ATM decides a language in space if examining configurations which do not modify tape cells beyond the cell from the left is sufficient. A language which is decided by some ATM in time for some constant is said to be in the class, and a language decided in space is said to be in the class.
Example
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 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 which 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 and space. 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.
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 proved the theorems
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. is the class of function in time beginning by existential state and alternating at most times. It is called the th level of the hierarchy. is the same classes, but beginning by a universal state, it is the complement of the language of. is defined similarly for space bounded computation.
Example
Consider the circuit minimization problem: given a circuit A computing a Boolean functionf 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.
Collapsing classes
It is said that a hierarchy collapses to level if every language in level of the hierarchy is in its level. As a corollary of the Immerman–Szelepcsényi theorem, the logarithmic space hierarchy collapses to its first level. As a corollary the hierarchy collapses to its first level when is space constructible.
Special cases
An alternating Turing machine in polynomial time with k alternations, starting in an existential state can decide all the problems in the class . These classes are sometimes denoted and, respectively. See the polynomial hierarchy article for details. Another special case of time hierarchies is the logarithmic hierarchy.
