DocumentCode :
2722094
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
fYear :
1990
fDate :
8-11 July 1990
Firstpage :
45
Lastpage :
54
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Structure in Complexity Theory Conference, 1990, Proceedings., Fifth Annual
Conference_Location :
Barcelona
Print_ISBN :
0-8186-6072-4
Type :
conf
DOI :
10.1109/SCT.1990.113953
Filename :
113953
Link To Document :
بازگشت