Relationships to Other Classes

Relationships to Other Classes

• IP = PSPACE
  • Proof based on algebraic properties of certain PSPACE characterizations.
  • Proof does not relativize.
• MIP - Multiple Prover Proof System
• MIP = NEXP
  • Proof extends other result by using a multilinearity test.

Previous slide

Next slide

Back to the first slide

View Graphic Version

Feldman - IP in PSPACE.

Lund, Fortnow, Karloff and Nisan and Shamir - PSPACE in IP.

Ben-Or, Goldwasser, Kilian and Wigderson - Defined MIP.

MIP - Separate provers - interrogation better.

Fortnow, Rompel and Sipser - MIP in NEXP.

Babai, Fortnow and Lund - NEXP in MIP.