What Are the Limits of Interactive Proofs: Why Does MIP Fall Within NEXP?

  • Context: Graduate 
  • Thread starter Thread starter Dragonfall
  • Start date Start date
  • Tags Tags
    Proof
Join the discussion
Registration is free. Start your own thread to ask a follow-up.
Sign up Log in
1 reply · 1K views
Dragonfall
Messages
1,023
Reaction score
5
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].
 
Physics news on Phys.org

Discussion

I'd have posted this in the CS subforums, but this is more of a theoretical question.