Editing Polynomial hierarchy (section)

===Alternating Turing machines definition===
An [[alternating Turing machine]] is a non-deterministic Turing machine with non-final states partitioned into existential and universal states. It is eventually accepting from its current configuration if: it is in an existential state and can transition into some eventually accepting configuration; or, it is in a universal state and every transition is into some eventually accepting configuration; or, it is in an accepting state.<ref>Arora and Barak, pp.99–100</ref>

We define <math>\Sigma_k^\mathrm{P}</math> to be the class of languages accepted by an alternating Turing machine in polynomial time such that the initial state is an existential state and every path the machine can take swaps at most ''k'' – 1 times between existential and universal states. We define <math>\Pi_k^\mathrm{P}</math> similarly, except that the initial state is a universal state.<ref>Arora and Barak, pp.100</ref>

If we omit the requirement of at most ''k'' – 1 swaps between the existential and universal states, so that we only require that our alternating Turing machine runs in polynomial time, then we have the definition of the class '''AP''', which is equal to '''[[PSPACE]]'''.<ref>Arora and Barak, pp.100</ref>