On the power of multi-prover interactive protocols

We look at complexity issues of interactive proof systems with multiple provers separated from each other. This model, developed by Ben-Or et al. (1988) allows the verifier to play the provers off each other. We show this model equivalent to an alternative interactive proof system model using oracles as provers. We also show that every language accepted by these models lies in nondeterministic exponential time. We exhibit a relativized world where a co-NP language does not have multiple prover interactive proofs. Finally, we show a simple example that one cannot parallelize multiple prover protocols as easily as the single prover model.

Authors

• Lance Fortnow
• John Rompel
• Michael Sipser

Keywords

No keywords are indexed for this paper.