1

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.

Thanks!

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.

flag
1 
 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. – Peter Shor Mar 2 2011 at 21:34
@Peter Shor: got it working. Thanks! – LowerBounds Mar 2 2011 at 22:18
@Moderators: Why is my question marked as too localized? – LowerBounds Mar 7 2011 at 17:27
See Peter Shor's comment here: meta.mathoverflow.net/discussion/922/… – JBL Mar 8 2011 at 0:00
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. – Peter Shor Mar 20 2011 at 21:33

closed as too localized by Andres Caicedo, Peter Shor, Bill Johnson, Mark Sapir, Gjergji Zaimi Mar 3 2011 at 19:48

1 Answer

0

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.

link|flag

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