|
On the possibility of performing any multi-prover interactive proof in constantly many rounds
O. V. Verbitskii
Abstract:
In 1990 Babai, Fortnow, and Lund built a two-prover interactive proof system for an $\operatorname{NEXP}$-complete set, thereby proving that the complexity classes $\operatorname{MIP}$ and $\operatorname{NEXP}$ coincide. In the present paper for an arbitrary $\operatorname{NEXP}$-set a two-prover interactive protocol is built with permissible error probability $1/3$, the number of rounds being bounded by a universal constant , i.e., it is proved that for some constant $c$ the classes $\operatorname{MIP}$ and $\operatorname{IP}(2,c)$ coincide.
Received: 12.12.1991
Citation:
O. V. Verbitskii, “On the possibility of performing any multi-prover interactive proof in constantly many rounds”, Izv. RAN. Ser. Mat., 57:3 (1993), 152–178; Russian Acad. Sci. Izv. Math., 42:3 (1994), 561–586
Linking options:
https://www.mathnet.ru/eng/im871https://doi.org/10.1070/IM1994v042n03ABEH001545 https://www.mathnet.ru/eng/im/v57/i3/p152
|
Statistics & downloads: |
Abstract page: | 234 | Russian version PDF: | 78 | English version PDF: | 6 | References: | 33 | First page: | 2 |
|