Title :
On bounded round multiprover interactive proof systems
Author :
Cai, Jin-Yi ; Condon, Anne ; Lipton, Richard J.
Author_Institution :
Dept. of Comput. Sci., Princeton Univ., NJ, USA
Abstract :
Bounded round multiprover interactive proof systems (MIPs) are compared with unbounded round interactive proof systems (IPSs). It is shown that for any constant ε, any language accepted by an unbounded round IPS has a bounded round, two-prover MIP that has error probability ε, 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
Keywords :
computational complexity; bounded round multiprover interactive proof systems; error probability; language; parallel; two-prover MIP; unbounded round interactive proof systems; Computer science; Contracts; Error probability; Polynomials; Protocols; Tail;
Conference_Titel :
Structure in Complexity Theory Conference, 1990, Proceedings., Fifth Annual
Conference_Location :
Barcelona
Print_ISBN :
0-8186-6072-4
DOI :
10.1109/SCT.1990.113953