DocumentCode
1570772
Title
On the power of multi-power interactive protocols
Author
Fortnow, Lance ; Rompel, John ; Sipser, Michael
Author_Institution
Lab. for Comput. Sci., MIT, Cambridge, MA, USA
fYear
1988
Firstpage
156
Lastpage
161
Abstract
A simple characterization of the power of the multipower model in terms of probabilistic oracle Turing machines is given. It is shown that languages that have single-prover interactive protocols also have two prover-bounded round protocols and that languages that have multiprover interactive protocols have two prover protocols and three prover-bounded round protocols. An oracle is given relative to which there exists a co-NP language, that is not accepted by any multiprover interactive protocol
Keywords
Turing machines; protocols; co-NP language; multiprover interactive protocols; power; probabilistic oracle Turing machines; three prover-bounded round protocols; two prover protocols; Computer science; Cryptography; Laboratories; Polynomials; Power system modeling; Protocols;
fLanguage
English
Publisher
ieee
Conference_Titel
Structure in Complexity Theory Conference, 1988. Proceedings., Third Annual
Conference_Location
Washington, DC
Print_ISBN
0-8186-0866-8
Type
conf
DOI
10.1109/SCT.1988.5275
Filename
5275
Link To Document