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.

UDC: 519.682

MSC: 03B35, 68T15, 03D15, 68Q15

Received: 12.12.1991

 English version: Russian Academy of Sciences. Izvestiya Mathematics, 1994, 42:3, 561–586

Bibliographic databases:

• 
• 
• 
•