Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols

The exact power of two-prover interactive proof systems (MIP) introduced by M. Ben-Or et al. (Proc. 20th Symp. on Theory of Computing, 1988, p. 113-31) is determined. In this system, two all-powerful noncommunicating provers convince a randomizing polynomial-time verifier in polynomial time that the input x belongs to the language L. It was previously suspected (and proved in a relativized sense) that coNP-complete languages do not admit such proof systems. In sharp contrast, it is shown that the class of languages having two-prover interactive proof systems is computable in nondeterministic exponential time (NEXP). This represents a further step demonstrating the unexpectedly immense power for randomization and interaction in efficient provability. >

Authors

• László Babai
• Lance Fortnow
• Carsten Lund

Keywords

• Protocols
• Polynomials
• Upper bound
• Joining processes
• Circuits
• Extrapolation
• Cryptography
• Graphics
• Interactive System
• Language Teaching
• Formal Verification
• Proof Of Theorem
• Input Size
• Multilinear
• Turing Machine
• Proportion Of Lines
• Probabilistic Polynomial Time
• Universal Quantifier