PSPACE is provable by two provers in one round

摘要

We show that every language in PSPACE, or equivalently, every language accepted by an unbounded round interactive proof system, ha a 1-round, 2-prover interactive proof system with exponentially small error probability. To obtain this result, we prove the correctness of a simple but powerful method for parallelizing 2-prover interactive proof systems to reduce their error.