Two-prover one-round proof systems: Their power and their problems

Abstract

We characterize the power of two-prover one-round (MIP(2,1)) proof systems, showing that MIP(2,1) = NEXPTIME. However, the following intriguing question remains open: Does parallel repetition decrease the error probability of MIP(1,1) proof systems? We use techniques based on quadratic programming to study this problem, and prove the parallel repetition conjecture in some special cases. Interestingly, our work leads to a general polynomial time heuristic for any NP-problem. We prove the effectiveness of this heuristic for several problems, such as computing the chromatic number of perfect graphs.