Alternation (complexity)

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 and independently by Kozen in 1976, with a joint journal publication in 1981.

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, 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.

Formally, a (one-tape) alternating Turing machine is a 5-tuple ${\displaystyle M=(Q,\Gamma ,\delta ,q_{0},g)}$ where

...
Wikipedia