×

On the power of multi-prover interactive protocols. (English) Zbl 0938.68824

Summary: We look at complexity issues of interactive proof systems with multiple provers separated from each other. This model, developed by M. Ben-Or et al. [in Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, Chicago, IL, 1988, 113-131, ACM, New York, 1988] allows the verifier to play the provers off each other. We show this model equivalent to an alternative interactive proof system model using oracles as provers. We also show that every language accepted by these models lies in nondeterministic exponential time. We exhibit a relativized world where a co-NP language does not have multiple prover interactive proofs. Finally, a simple example shows that one cannot parallelize multiple prover protocols as easily as the single prover model.

MSC:

68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arora, S.; Lund, C.; Motwani, R.; Sudan, M.; Szegedy, M.: Proof verification and hardness of approximation problems. Proc. 33rd IEEE symposium on foundations of computer science, 14-23 (1992) · Zbl 0977.68539
[2] Arora, S.; Safra, S.: Probabilistic checking of proofs: A new characterization of NP. Proc. 33rd IEEE symposium on foundations of computer science, 2-13 (1992) · Zbl 0945.68516
[3] Babai, L.: Trading group theory for randomness. Proc. 17th ACM symposium on the theory of computing, 421-429 (1985)
[4] Babai, L.; Fortnow, L.; Lund, C.: Non-deterministic exponential time has two-prover interactive protocols. Computational complexity 1, No. 1, 3-40 (1991) · Zbl 0774.68041
[5] Babai, L.; Moran, S.: Arthur-merlin games: A randomized proof system, and a hierarchy of complexity classes. J. comput. System sci. 36, No. 2, 254-276 (1988) · Zbl 0652.03029
[6] Ben-Or, M.; Goldwasser, S.; Kilian, J.; Wigderson, A.: Multi-prover interactive proofs: how to remove intractability assumptions. Proc. 20th ACM symposium on the theory of computing, 113-131 (1988)
[7] Blum, M.; Kannan, S.: Designing programs that check their work. Proc. 21st ACM symposium on the theory of computing, 86-97 (1989) · Zbl 0886.68046
[8] Blum, M.; Luby, M.; Rubinfeld, R.: Self-testing and self-correcting programs, with applications to numerical programs. Proc. 22nd ACM symposium on the theory of computing, 73-83 (1990)
[9] Boppana, R.; Håstad, J.; Zachos, S.: Does co-NP have short interactive proofs?. Inform. process. Lett. 25, No. 2, 127-132 (1987) · Zbl 0653.68037
[10] Cai, J.; Condon, A.; Lipton, R.: On bounded round multi-prover interactive proof systems. Proc. 5th IEEE structure in complexity theory conference, 45-54 (1990)
[11] Cai, J.; Condon, A.; Lipton, R.: PSAPCE is provable by two provers in one round. Proc. 6th IEEE structure in complexity theory conference, 110-115 (1991)
[12] Cai, J.; Condon, A.; Lipton, R.: On games of incomplete information. Theoret. comput. Sci. 103, No. 1, 25-38 (1992) · Zbl 0757.90090
[13] Feige, U.: On the success probability of the two provers in one round proof systems. Proc. 6th IEEE structure in complexity theory conference, 116-123 (1991)
[14] Feige, U.; Goldwasser, S.; Lovász, L.; Safra, S.; Szegedy, M.: Approximating clique is almost NP-complete. Proc. 32nd IEEE symposium on foundations of computer science, 2-12 (1991)
[15] Feige, U.; Lovász, L.: Two-prover one-round proof systems: their power and their problems. Proc. 24th ACM symposium on the theory of computing, 733-744 (1992)
[16] Feldman, P.; Micali, S.: From scratch to Byzantine agreement in constant expected time. Proc. 20th ACM symposium on the theory of computing, 148-161 (1988)
[17] Fortnow, L.: The complexity of perfect zero-knowledge. Advances in computing research 5, 327-343 (1989)
[18] Fortnow, L.: Complexity-theoretic aspects of interactive proof systems. Tech report MIT/LCS/TR-447 (1989)
[19] Fortnow, L.; Rompel, J.; Sipser, M.: On the power of multi-prover interactive protocols. Proc. 3rd IEEE structure in complexity theory conference, 156-161 (1988)
[20] Fortnow, L.; Sipser, M.: Are there interactive protocols for co-NP languages?. Inform. process. Lett. 28, 249-251 (1988) · Zbl 0668.68054
[21] Furer, M.; Goldreich, O.; Mansour, Y.; Sipser, M.; Zachos, S.: On completeness and soundness in interactive proof systems. Advances in computing research 5, 429-442 (1989)
[22] Goldreich, O.; Micali, S.; Wigderson, A.: Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. ACM 38, No. 3, 691-729 (1991) · Zbl 0799.68101
[23] Goldwasser, S.; Micali, S.; Rackoff, C.: The knowledge complexity of interactive proof-systems. SIAM J. Comput. 18, No. 1, 186-208 (1989) · Zbl 0677.68062
[24] Goldwasser, S.; Sipser, M.: Private coins versus public coins in interactive proof systems. Advances in computing research 5, 73-90 (1989)
[25] Kilian, J.: Uses of randomness in algorithms and protocols. ACM distinguised dissertation (1990)
[26] Lapidot, D.; Shamir, A.: Fully parallelized multi prover protocols for NEXP-time. Proc. 32nd IEEE symposium on foundations of computer science, 13-18 (1991) · Zbl 0877.68078
[27] Lund, C.; Fortnow, L.; Karloff, H.; Nisan, N.: Algebraic methods for interactive proof systems. J. ACM 39, No. 4, 859-868 (1992) · Zbl 0799.68097
[28] Papadimitriou, C.; Yannakakis, M.: Optimization, approximation, and complexity classes. J. comput. System sci. 43, 425-440 (1991) · Zbl 0765.68036
[29] Shamir, A.: Ip = pspace. J. ACM 39, No. 4, 869-877 (1992) · Zbl 0799.68096
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.