Title :
On the success probability of the two provers in one-round proof systems
Author_Institution :
Dept. of Comput. Sci., Princeton Univ., NJ, USA
fDate :
30 Jun-3 Jul 1991
Abstract :
The author addresses the problem of reducing the error probability of two-prover one-round proof systems, without increasing the number of provers or the number of rounds. An example, the noninteractive agreement protocol, where executing such a protocol twice in parallel does not decrease the error probability at all is constructed. Upper bounds on the error probability of specific classes of protocols are proved. As a corollary, it is shown that every NEXPTIME language has a one-round two-prover proof system with constant error probability
Keywords :
computational complexity; probability; NEXPTIME language; error probability; noninteractive agreement protocol; one-round proof systems; success probability; two provers; upper bounds; Computer errors; Computer science; Error probability; Polynomials; Power system modeling; Probability distribution; Protocols; Upper bound;
Conference_Titel :
Structure in Complexity Theory Conference, 1991., Proceedings of the Sixth Annual
Conference_Location :
Chicago, IL
Print_ISBN :
0-8186-2255-5
DOI :
10.1109/SCT.1991.160251
