{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:49:42Z","timestamp":1781077782162,"version":"3.54.1"},"reference-count":29,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[1994,11,1]],"date-time":"1994-11-01T00:00:00Z","timestamp":783648000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":6833,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[1994,11]]},"DOI":"10.1016\/0304-3975(94)90251-8","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T03:47:32Z","timestamp":1027655252000},"page":"545-557","source":"Crossref","is-referenced-by-count":93,"title":["On the power of multi-prover interactive protocols"],"prefix":"10.1016","volume":"134","author":[{"given":"Lance","family":"Fortnow","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John","family":"Rompel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Sipser","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/0304-3975(94)90251-8_BIB1","series-title":"Proc. 33rd IEEE Symposium on Foundations of Computer Science","first-page":"14","article-title":"Proof verification and hardness of approximation problems","author":"Arora","year":"1992"},{"key":"10.1016\/0304-3975(94)90251-8_BIB2","series-title":"Proc. 33rd IEEE Symposium on Foundations of Computer Science","first-page":"2","article-title":"Probabilistic checking of proofs: A new characterization of NP","author":"Arora","year":"1992"},{"key":"10.1016\/0304-3975(94)90251-8_BIB3","series-title":"Proc. 17th ACM Symposium on the Theory of Computing","first-page":"421","article-title":"Trading group theory for randomness","author":"Babai","year":"1985"},{"issue":"1","key":"10.1016\/0304-3975(94)90251-8_BIB4","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF01200056","article-title":"Non-deterministic exponential time has two-prover interactive protocols","volume":"1","author":"Babai","year":"1991","journal-title":"Computational Complexity"},{"issue":"2","key":"10.1016\/0304-3975(94)90251-8_BIB5","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1016\/0022-0000(88)90028-1","article-title":"Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes","volume":"36","author":"Babai","year":"1988","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0304-3975(94)90251-8_BIB6","series-title":"Proc. 20th ACM Symposium on the Theory of Computing","first-page":"113","article-title":"Multi-prover interactive proofs: How to remove intractability assumptions","author":"Ben-Or","year":"1988"},{"key":"10.1016\/0304-3975(94)90251-8_BIB7","series-title":"Proc. 21st ACM Symposium on the Theory of Computing","first-page":"86","article-title":"Designing programs that check their work","author":"Blum","year":"1989"},{"key":"10.1016\/0304-3975(94)90251-8_BIB8","series-title":"Proc. 22nd ACM Symposium on the Theory of Computing","first-page":"73","article-title":"Self-testing and self-correcting programs, with applications to numerical programs","author":"Blum","year":"1990"},{"issue":"2","key":"10.1016\/0304-3975(94)90251-8_BIB9","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0020-0190(87)90232-8","article-title":"Does co-NP have short interactive proofs?","volume":"25","author":"Boppana","year":"1987","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0304-3975(94)90251-8_BIB10","series-title":"Proc. 5th IEEE Structure in Complexity Theory Conference","first-page":"45","article-title":"On bounded round multi-prover interactive proof systems","author":"Cai","year":"1990"},{"key":"10.1016\/0304-3975(94)90251-8_BIB11","series-title":"Proc. 6th IEEE Structure in Complexity Theory Conference","first-page":"110","article-title":"PSAPCE is provable by two provers in one round","author":"Cai","year":"1991"},{"issue":"1","key":"10.1016\/0304-3975(94)90251-8_BIB12","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/0304-3975(92)90085-T","article-title":"On games of incomplete information","volume":"103","author":"Cai","year":"1992","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(94)90251-8_BIB13","series-title":"Proc. 6th IEEE Structure in Complexity Theory Conference","first-page":"116","article-title":"On the success probability of the two provers in one round proof systems","author":"Feige","year":"1991"},{"key":"10.1016\/0304-3975(94)90251-8_BIB14","series-title":"Proc. 32nd IEEE Symposium on Foundations of Computer Science","first-page":"2","article-title":"Approximating clique is almost NP-complete","author":"Feige","year":"1991"},{"key":"10.1016\/0304-3975(94)90251-8_BIB15","series-title":"Proc. 24th ACM Symposium on the Theory of Computing","first-page":"733","article-title":"Two-prover one-round proof systems: Their power and their problems","author":"Feige","year":"1992"},{"key":"10.1016\/0304-3975(94)90251-8_BIB16","series-title":"Proc. 20th ACM Symposium on the Theory of Computing","first-page":"148","article-title":"From scratch to byzantine agreement in constant expected time","author":"Feldman","year":"1988"},{"key":"10.1016\/0304-3975(94)90251-8_BIB17","series-title":"Randomness and Computation","first-page":"327","article-title":"The complexity of perfect zero-knowledge","volume":"Vol. 5","author":"Fortnow","year":"1989"},{"key":"10.1016\/0304-3975(94)90251-8_BIB18","series-title":"Ph.D. thesis","article-title":"Complexity-theoretic aspects of interactive proof systems","author":"Fortnow","year":"1989"},{"key":"10.1016\/0304-3975(94)90251-8_BIB19","series-title":"Proc. 3rd IEEE Structure in Complexity Theory Conference","first-page":"156","article-title":"On the power of multi-prover interactive protocols","author":"Fortnow","year":"1988"},{"key":"10.1016\/0304-3975(94)90251-8_BIB20","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0020-0190(88)90199-8","article-title":"Are there interactive protocols for co-NP languages?","volume":"28","author":"Fortnow","year":"1988","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0304-3975(94)90251-8_BIB21","series-title":"Randomness and Computation","first-page":"429","article-title":"On completeness and soundness in interactive proof systems","volume":"Vol. 5","author":"Furer","year":"1989"},{"issue":"3","key":"10.1016\/0304-3975(94)90251-8_BIB22","doi-asserted-by":"crossref","first-page":"691","DOI":"10.1145\/116825.116852","article-title":"Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems","volume":"38","author":"Goldreich","year":"1991","journal-title":"J. ACM"},{"issue":"1","key":"10.1016\/0304-3975(94)90251-8_BIB23","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1137\/0218012","article-title":"The knowledge complexity of interactive proof-systems","volume":"18","author":"Goldwasser","year":"1989","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(94)90251-8_BIB24","series-title":"Randomness and Computation","first-page":"73","article-title":"Private coins versus public coins in interactive proof systems","volume":"Vol. 5","author":"Goldwasser","year":"1989"},{"key":"10.1016\/0304-3975(94)90251-8_BIB25","series-title":"ACM Distinguised Dissertation","article-title":"Uses of Randomness in Algorithms and Protocols","author":"Kilian","year":"1990"},{"key":"10.1016\/0304-3975(94)90251-8_BIB26","series-title":"Proc. 32nd IEEE Symposium on Foundations of Computer Science","first-page":"13","article-title":"Fully parallelized multi prover protocols for NEXP-time","author":"Lapidot","year":"1991"},{"issue":"4","key":"10.1016\/0304-3975(94)90251-8_BIB27","doi-asserted-by":"crossref","first-page":"859","DOI":"10.1145\/146585.146605","article-title":"Algebraic methods for interactive proof systems","volume":"39","author":"Lund","year":"1992","journal-title":"J. ACM"},{"key":"10.1016\/0304-3975(94)90251-8_BIB28","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","article-title":"Optimization, approximation, and complexity classes","volume":"43","author":"Papadimitriou","year":"1991","journal-title":"J. Comput. System Sci."},{"issue":"4","key":"10.1016\/0304-3975(94)90251-8_BIB29","doi-asserted-by":"crossref","first-page":"869","DOI":"10.1145\/146585.146609","article-title":"IP = PSPACE","volume":"39","author":"Shamir","year":"1992","journal-title":"J. ACM"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0304397594902518?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0304397594902518?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,13]],"date-time":"2019-04-13T03:51:36Z","timestamp":1555127496000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0304397594902518"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,11]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1994,11]]}},"alternative-id":["0304397594902518"],"URL":"https:\/\/doi.org\/10.1016\/0304-3975(94)90251-8","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[1994,11]]}}}