On bounded round multiprover interactive proof systems
J. Cai, Anne Condon, R.J. Lipton · 2002
Bounded round multiprover interactive proof systems (MIPs) are compared with unbounded round interactive proof systems (IPSs). It is shown that for any constant epsilon , any language accepted by an unbounded round IPS has a bounded round, two-prover MIP that has error probability epsilon , resolving an open problem of L. Fortnow et al. (1988). To obtain this result, it is shown that a certain one-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.>