ATMs: are the languages decidable in polynomial time are the languages decidable in polynomial space are the languages decidable in exponential time 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 ALOGSPACE = P AP = PSPACE APSPACE = EXPTIME AEXPTIME = EXPSPACE when and . A more general form of these relationships is expressed by the parallel computation thesis. Bounded alternation Definition An alternating Turing machine with k alternations is an alternating Turing machine that 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.) is the class of languages decidable in time by a machine beginning in an existential state and alternating at most times. It is called the th level of the hierarchy. 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. 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 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). 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 (respectively, universal) state can decide all the problems in the class (respectively, ). These classes