ALTERNATING TURING MACHINE

Quantified Boolean Formula

(Ax)(Ey)(Az)(some formula here).

The quantifiers are quantifiying over boolean values.

In this case, you start in a universal state.  In this universal state, you transition to other universal states as you start your evaluation process.  Because the ATM is also a NTM, you nondeterministcally have a states where x is TRUE and a set of states where x is FALSE.  And these sets of states will plug in the appropriate value into the formula and then remove the quantifier from the formula.

So we now have (Ey)(Az)(some formula without an x)

Now we transition to a series of existential states and nondeterministically try both TRUE and FALSE for y, building a new formula (Az)(some formula over z).

Then we switch to universal states, try both values for z and if we get a true answer go to an "basic" accept state.  If we get a false answer go to a "basic" reject state.

("Basic" Accept state is a universal state which transitions nowhere.  "Basic" Reject state is an existential state which transitions nowhere.)

A universal state is an "accept state" if all of its transitions lead to an accept state.  So, if in the case of (Az)(some formula over z) there is a value of z that makes formula false, all the transitions leading to the computation of false have to be reject states.  So, working backwards, when we're at the part of our computation where we're trying to decide (Az)(some formula), if there is one path that leads to failure the state in which we switched to universal is also a reject state as it does have a transition that leads to reject.  If, however, both TRUE and FALSE cause the formula to evaluate to true, then we're an accept state since all transitions lead to an accept state.

Continuing to work backward, the existential state that got us to this point will be an accept state if the (Az) formula is true and reject if the (Az) formula is false.  And so all the states leading to this will be false.  (Because all the transitions we're making at this part of the computation involves computing that (Az) formula.  These will either all be reject states or all be accept states.

When we get back to the (Ey) formula, that's we nondeterministically try TRUE and FALSE for y.  The choice of true will leads us either to an accept state (if it eventually works out true for the choice of y being true) or a reject state (if it eventually works out false).  Similarly, the choice of false will leads either to an accept or a reject state.  Since we are in an existential state, if either choice leads to an accept state then we are presently in an accept state.  If both choices lead to a reject state then we are in a reject state.

Moving backwards again the (Ax) will be rejected unless both choices for x lead to an accept state.  If both do, the ATM starts in an accept state.  If one or both do not, then the ATM starts in a reject state.

And, this is the definition of acceptance in an ATM:  it starts in an accept state.

QBF is known to be PSPACE-complete.  It is not known to be in any specific level of the polynomial hierarchy.  (But PSPACE is a superset of the union of all the levels of the hierarchy.)