1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Interactive proof and PSPACE
  1. A proof. (Replies: 2)

  2. P=PSPACE theorem (Replies: 1)

  3. Proof help? (Replies: 4)

Loading...