Skip to main content
MathOverflow

Return to Question

Post Closed as "too localized" by Andrés E. Caicedo, Peter Shor, Bill Johnson, user6976, Gjergji Zaimi
added 259 characters in body
Source Link
LowerBounds
LowerBounds
  • 663
  • 8
  • 22

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.

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!

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.

Source Link
LowerBounds
LowerBounds
  • 663
  • 8
  • 22

Proving APSPACE = EXP

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!