|
TR-237-89
On Bounded Round Multi-Prover Interactive Proof Systems |
|
| Authors: | Cai, Jin-Yi, Condon, Anne, Lipton, Richard J. |
| Date: | December 1989 |
| Pages: | 16 |
| Download Formats: | [PDF] |
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. |
|