Alternating Turing machine

In computational complexity theory, an alternating Turing machine (ATM) is a non-deterministic Turing machine with a rule for accepting computations that generalizes the rules behind the complexity classes NP and co-NP. NP uses the existential mode, where a computation accepts if any choice leads to an accepting state, and co-NP uses the universal mode, where it accepts only if every choice does. An alternating machine divides its states into existential and universal sets, so a computation alternates between the two modes. The concept was set forth by Chandra and Stockmeyer and independently by Kozen in 1976, with a joint journal publication in 1981. A natural problem for these machines is the quantified Boolean formula problem, where the machine branches existentially on existentially quantified variables and universally on universally quantified ones. Resource-bounded alternating machines define classes such as the languages decidable in polynomial time or in polynomial space, and machines limited to a fixed number of alternations lead to the polynomial hierarchy.