On Bounded Round Multi-Prover Interactive Proof Systems
Report ID: TR-237-89Author: Cai, Jin-Yi / Lipton, Richard J. / Condon, Anne
Date: 1989-12-00
Pages: 16
Download Formats: |PDF|
Abstract:
We compare bounded round multi-prover interactive proof systems (MIPs) with unbounded round interactive proof systems (IPSes). We show that for any constant epsilon, any language accepted by an unbounded round IPS has a bounded round, 2-prover MIP that has error probability epsilon, resolving an open problem of Fortnow, Rompel and Sipser. To obtain this result, we show that a certain 1-round MIP that simulates the computation of an unbounded round IPS can be executed many times in parallel to significantly reduce its probability of error.