AP = Alternating Polynomial Time PSPACE = Polynomial Space APSPACE = Alternating Polynomial Space EXP = Exponential time
Proving AP = PSPACE is fairly easy: 1) TQBF is PSPACE complete 2) AP can solve TQBF buy (forall/there-exist)-ing down the for-all/there-exists of TQBF, and evalute it. 3) Encoding AP in TQBF is easy as well -- encode the TM as a SAT formula, then express the TM alternations as for-all/there-exists
Now, how do we use this to prove APSPACE = EXP? I'm currently stuck on finding a EXP-complete or APSPACE-complete problem to show the other can solve.
This is self study, exercise 5.7 of Computational Complexity a Modern Approach.
To the jaded people who think this is homework question -- look at my previous questions; they're all over the place -- not typical of a course, more typical of self study.