Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Interactive proof and PSPACE

  1. Oct 23, 2012 #1
    You can prove that [tex]\mathbf{IP} \subset \mathbf{PSPACE}[/tex] by traversing the exponentially large decision tree of the prover, which takes only polynomial amount of space at a time.

    Why can't you do the same in the case of multiple provers? You'd traverse polynomially many trees at a time instead of one, but that should only require poly space. Instead, [tex]\mathbf{MIP} \subset \mathbf{NEXP}[/tex].
  2. jcsd
  3. Oct 23, 2012 #2
    I'd have posted this in the CS subforums, but this is more of a theoretical question.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook