1
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 2
    $\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
    Commented Mar 2, 2011 at 21:34
  • $\begingroup$ @Peter Shor: got it working. Thanks! $\endgroup$
    – LowerBounds
    Commented Mar 2, 2011 at 22:18
  • $\begingroup$ @Moderators: Why is my question marked as too localized? $\endgroup$
    – LowerBounds
    Commented Mar 7, 2011 at 17:27
  • $\begingroup$ See Peter Shor's comment here: tea.mathoverflow.net/discussion/922/… $\endgroup$
    – JBL
    Commented Mar 8, 2011 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
    Commented Mar 20, 2011 at 21:33

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .