On the possibility of performing any multi-prover interactive proof in constantly many rounds

O. V. Verbitskii

Izvestiya. Mathematics , Tome 42 (1994) no. 3, pp. 561-586.

Résumé

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.

Bibliographie

[1] Bernshtein S. N., Teoriya veroyatnostei, GITTL, M.-L., 1946

[2] Vozenkraft Dzh. M., Reiffen B., Posledovatelnoe dekodirovanie, IL, M., 1963

[3] Babai L., “Trading group theory for randomness”, Proc. 17th ACM Symp. on Theory of Computing, 1985, 421–429

[4] Babai L., Fortnow L., Lund C., “Non-deterministic exponential time has two-prover interactive protocols”, Computational complexity, 1:1 (1991), 3–40 | DOI | MR | Zbl

[5] Ben-Or M., Goldwasser S., Kilian J., Wigderson A., “Multi-prover interactive proofs: how to remove intractability assumptions”, Proc. 20th ACM Symp. on Theory of Computing, 1988, 113–131

[6] Cai J.-y., Condon A., Lipton R. J., “Playing games of incomplete information”, Proc. 7th Symp. on Theoretical Aspects of Computer Science, LNCS, 415, 1990, 58–69 | Zbl

[7] Cai J.-y., Condon A., Lipton R. J., “On bounded round multi-prover interactive proof systems”, Proc. 5th Conf. on Structure in Complexity Theory, 1990, 45–54 | MR

[8] Cai J.-y., Condon A., Lipton R. J., “$\mathrm{PSPACE}$ is provable by two provers in one round”, Proc. 6th Conf. on Structure in Complexity Theory, 1991, 110–115

[9] Feige U., “On the success probability of the two provers in one round proof systems”, Proc. 6th Conf. on Structure in Complexity Theory, 1991, 116–123

[10] Fortnow L., Complexity-theoretic aspects of interactive proof systems, Ph.D. Thesis. Tech. Report # MIT/LCS/TR-447. MIT, 1989

[11] Fortnow L., Rompel J., Sipser M., “On the power of multi-prover interactive protocols”, Proc. 3rd Conf. on Structure in Complexity Theory, 1988, 156–161

[12] Fortnow L., Rompel J., Sipser M., “Errata for On the power of multi-prover interactive protocols”, Proc. 5th Conf. on Sturcture in Complexity Theory, 1990, 318–319

[13] Goldreich O., Micali S., Wigderson A., “Proof that yield nothing but their validity and a methodology for protocol design”, Proc. 27th Symp. on Foundations of Computer Science, 1986, 174–187

[14] Goldwasser S., Micali S., Rackqff C., “The knowledge complexity of interactive proof-systems”, SIAM J. Computing, 18:1 (1989), 186–208 | DOI | MR | Zbl

[15] Goldwasser S., Sipser M., “Private coins versus public coins ini interactive proof-systems”, Proc. 18th ACM Symp. on Theory of Computing, 1986, 59–68

[16] Kilian J., “Strong separation models of multi-prover interactive proofs”, DIMACS Workshop on Cryptography, 1990

[17] Lapidot D., Shamir A., “Fully parallelized multi-prover protocols for NEXP-time”, Proc. 32nd Symp. on Foundations of Computer Science, 1991, 13–18

[18] Lund C., Fortnow L., Karloff H., Nisan N., “Algebraic methods for interactive proof systems”, Proc. 31st Symp. on Foundations of Computer Science, I, 1990, 2–10 | MR

[19] Shamir A., “$\mathrm{IP=PSPACE}$”, Proc. 31st Symp. on Foundations of Computer Science, 1, 1990, 11–15 | MR

[20] Shen A., $\mathrm{IP=PSPACE}$: simplified proof, Preprint, 1990 | MR

[21] Feige U., Lovász L., “Two-prover one-round proof systems: their power and their problems”, Proc. 24th ACM Symp. on Theory of Computing, 1992, 733–744