Two-prover one-round proof systems: Their power and their problems
Uriel Feige, László Lovász · Symposium on the Theory of Computing · 1992
We characterize the power of two-prover one-round (MI’P(2, 1)) proof systems, showing that M1P(2, 1) = NEXPTIME. However, the following intriguing question remains open: Does parallel repetition decrease the error probability y of MlP(2, 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.