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.


closed as too localized by Andrés E. Caicedo, Peter Shor, Bill Johnson, Mark Sapir, Gjergji Zaimi Mar 3 '11 at 19:48

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ If you have access to it, you could always look at Chandra, Kozen and Stockmeyer's original paper(portal.acm.org/citation.cfm?doid=322234.322243). Their problem is: given an alternating PSPACE Turing machine, does it accept the input? Showing APSPACE $\subseteq$ EXP isn't too hard. To go the other way, they use the question: given an exponential-time Turing machine on input $x$, does it accept, and show it's in APSPACE. $\endgroup$ – Peter Shor Mar 2 '11 at 21:34
  • $\begingroup$ @Peter Shor: got it working. Thanks! $\endgroup$ – LowerBounds Mar 2 '11 at 22:18
  • $\begingroup$ @Moderators: Why is my question marked as too localized? $\endgroup$ – LowerBounds Mar 7 '11 at 17:27
  • $\begingroup$ See Peter Shor's comment here: tea.mathoverflow.net/discussion/922/… $\endgroup$ – JBL Mar 8 '11 at 0:00
  • $\begingroup$ In my comment, maybe I was wrong that this question would be closed on cstheory stackexchange. But certainly the similar question: why is APTIME = PSPACE, would be closed, as it is a standard result in any complexity theory course. This result was originally proved in the same paper, and has essentially the same proof. $\endgroup$ – Peter Shor Mar 20 '11 at 21:33

http://en.wikipedia.org/wiki/APSPACE (redirects to EXPTIME) also has a reference. That's often the first place to look.

It occurs to me that you might also like http://cstheory.stackexchange.com if you don't kbow about it already.


Not the answer you're looking for? Browse other questions tagged or ask your own question.