ON THE POSSIBILITY OF PERFORMING ANY MULTI-PROVER INTERACTIVE PROOF IN CONSTANTLY MANY ROUNDS
Олег Васильевич Вербицкий · Izvestiya Mathematics · 1994
In 1990 Babai, Fortnow, and Lund built a two-prover interactive proof system for an NEXP-complete set, thereby proving that the complexity classes MIP and NEXP coincide. In the present paper for an arbitrary 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 c, i.e., it is proved that for some constant c the classes MIP and IP(2,c) coincide.