{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:56:09Z","timestamp":1781078169549,"version":"3.54.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1991,3,1]],"date-time":"1991-03-01T00:00:00Z","timestamp":667785600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Complexity"],"published-print":{"date-parts":[[1991,3]]},"DOI":"10.1007\/bf01200056","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T13:41:22Z","timestamp":1109252482000},"page":"3-40","source":"Crossref","is-referenced-by-count":387,"title":["Non-deterministic exponential time has two-prover interactive protocols"],"prefix":"10.1007","volume":"1","author":[{"given":"L\ufffdszl\ufffd","family":"Babai","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lance","family":"Fortnow","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Carsten","family":"Lund","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A. V. Aho, J. E. Hopcroft, andJ. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading MA, 1974."},{"key":"CR2","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1017\/S0269964800000267","volume":"1","author":"D. Aldous","year":"1987","unstructured":"D. Aldous, On the Markov chain simulation method for uniform combinatorial distributions and simulated annealing.Probability in the Engineering and Informational Sciences 1 (1987), 33?46.","journal-title":"Probability in the Engineering and Informational Sciences"},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"L. Babai, Trading group theory for randomness, inProc. 17th Ann. ACM Symp. Theory of Computing, 1985, 421?429.","DOI":"10.1145\/22145.22192"},{"key":"CR4","doi-asserted-by":"crossref","unstructured":"L. Babai, E-mail and the unexpected power of interaction, in: Proc. 5th Ann. IEEE Structures in Complexity Theory Conf., 1990, 30?44.","DOI":"10.1109\/SCT.1990.113952"},{"key":"CR5","first-page":"27","volume":"12","author":"L. Babai","year":"1982","unstructured":"L. Babai andP. Erd?s, Representation of group elements as short products,Annals of Discrete Mathematics 12 (1982), 27?30.","journal-title":"Annals of Discrete Mathematics"},{"key":"CR6","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF01200057","volume":"1","author":"L. Babai","year":"1991","unstructured":"L. Babai andL. Fortnow, Arithmetization: a new method in structural complexity theory,Computational Complexity 1 (1991), 41?66. (Preliminary version appeared as: A characterization of #P by arithmetic straight line programs, inProc. 31st Ann. IEEE Symp. Foundations of Comp. Sci., 1990, 26?34.)","journal-title":"Computational Complexity"},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"L. Babai, L. Fortnow, L. Levin, and M. Szegedy, Checking computations in polylogarithmic time, in:Proc 23rd ACM Symp. Theory of Computing, 1991, to appear.","DOI":"10.1145\/103418.103428"},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"L. Babai, L. Fortnow, and C. Lund, Non-deterministic exponential time has two-prover interactive protocols (extended abstract),Proc. 31st Ann. IEEE Symp. Found. Comp. Sci., 1990, 16?25.","DOI":"10.1109\/FSCS.1990.89520"},{"key":"CR9","unstructured":"L. Babai and P. Frankl,Linear Algebra Methods in Combinatorics, I, Preliminary Version, University of Chicago, Dept. C. S. 1988."},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"D. Beaver and J. Feigenbaum, Hiding instances in multioracle queries, inProc. 7th Symp. on Theoretical Aspects of Comp. Sci. Lecture Notes in Comp. Sci. 415 (1990), 37?48.","DOI":"10.1007\/3-540-52282-4_30"},{"key":"CR11","doi-asserted-by":"crossref","unstructured":"M. Ben-Or, S. Goldwasser, J. Kilian, and A. Wigderson, Multiprover interactive proofs: How to remove the intractability assumptions, inProc. 20th Ann. ACM Symp. Theory of Computing, 1988, 113?131.","DOI":"10.1145\/62212.62223"},{"key":"CR12","doi-asserted-by":"crossref","unstructured":"M. Blum and S. Kannan, Designing programs that check their work, inProc. 21st Ann. ACM Symp. Theory of Computing, 1989, 86?97.","DOI":"10.1145\/73007.73015"},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"M. Blum, M. Luby, and R. Rubinfeld, Self-testing and self-correcting programs, with applications to numerical programs, inProc. 22nd Ann. ACM Symp. Theory of Computing, 1990, 73?83.","DOI":"10.1145\/100216.100225"},{"key":"CR14","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1016\/0022-0000(88)90028-1","volume":"36","author":"L. Babai","year":"1988","unstructured":"L. Babai andS. Moran, Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes.J. Comp. Sys. Sci. 36 (1988), 254?276.","journal-title":"J. Comp. Sys. Sci."},{"key":"CR15","unstructured":"J. Cai, PSPACE is provable by two provers in one round, manuscript, 1990."},{"key":"CR16","doi-asserted-by":"crossref","unstructured":"S. A. Cook, The complexity of theorem proving procedures, inProc. 3rd Ann. ACM Symp. Theory of Computing 1971, 151?158.","DOI":"10.1145\/800157.805047"},{"key":"CR17","unstructured":"U. Feige, S. Goldwasser, L. Lov\u00e1sz, and S. Safra, On the complexity of clique approximation, in preparation."},{"key":"CR18","unstructured":"P. Feldman, The Optimum Prover lives inPSPACE, manuscript, 1986."},{"key":"CR19","unstructured":"L. Fortnow, The Complexity of Perfect Zero-Knowledge, In S. Micali, ed.,Randomness and Computation, Advances in Computing Research 5 (1989), 327?343."},{"key":"CR20","unstructured":"L. Fortnow, Complexity-Theoretic Aspects of Interactive Proof Systems, Ph.D. Thesis,Massachusetts Institute of Technology, Laboratory for Computer Science, Tech. Report MIT\/LCS\/TR-447 1989."},{"key":"CR21","doi-asserted-by":"crossref","unstructured":"L. Fortnow, J. Rompel, and M. Sipser, On the power of multiprover interactive protocols,Proc. 3rd Structure in Complexity Theory Conf., 1988, 156?161.","DOI":"10.1109\/SCT.1988.5275"},{"key":"CR22","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0020-0190(88)90199-8","volume":"28","author":"L. Fortnow","year":"1988","unstructured":"L. Fortnow andM. Sipser, Are there interactive protocols for co-NP languages?,Inf. Process. Letters 28 (1988), 249?251.","journal-title":"Inf. Process. Letters"},{"key":"CR23","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1137\/0218012","volume":"18","author":"S. Goldwasser","year":"1989","unstructured":"S. Goldwasser, S. Micali, andC. Rackoff, The knowledge complexity of interactive proofs,SIAM J. Comput. 18 (1989), 186?208. (Preliminary version appeared inProc. 18th Ann. ACM Symp. Theory of Computing, 1985, 291?304.)","journal-title":"SIAM J. Comput."},{"key":"CR24","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1016\/S0019-9958(85)80004-8","volume":"65","author":"J. Hartmanis","year":"1985","unstructured":"J. Hartmanis, N. Immerman, andV. Sewelson, Sparse sets inNP-P: EXPTIME versusNEXPTIME, Inf. and Control 65 (1985), 158?181.","journal-title":"Inf. and Control"},{"key":"CR25","first-page":"231","volume":"71","author":"H. Heller","year":"1986","unstructured":"H. Heller On Relativized Exponential and Probabilistic Complexity Classes,Information and Computation 71 (1986), 231?243.","journal-title":"Information and Computation"},{"key":"CR26","doi-asserted-by":"crossref","unstructured":"R. Karp, R. Lipton, Some Connections between Nonuniform and Uniform Complexity Classes,Proc. 12th Ann. ACM Symp. Theory of Computing, 1980, 302?309.","DOI":"10.1145\/800141.804678"},{"key":"CR27","first-page":"265","volume":"9","author":"L. Levin","year":"1973","unstructured":"L. Levin, Universal'ny\u00eee pereborny\u00eee zadachi (Universal search problems, in Russian),Problemy Peredachi Informatsii 9 (1973), 265?266. A corrected English translation appears in an appendix to Trakhtenbrot [39].","journal-title":"Problemy Peredachi Informatsii"},{"key":"CR28","unstructured":"R. Lipton, New directions in testing, inProceedings of the DIMACS Workshop on Distributed Computing and Cryptography, 1989, to appear."},{"key":"CR29","unstructured":"C. Lund, L. Fortnow, H. Karloff, and N. Nisan, Algebraic methods for interactive proof systems, inProc. 31st Ann. IEEE Symp. Foundations of Comp. Sci., 1990, 1?10."},{"key":"CR30","doi-asserted-by":"crossref","first-page":"573","DOI":"10.1007\/BFb0036938","volume":"154","author":"P. Orponen","year":"1983","unstructured":"P. Orponen, Complexity Classes of Alternating Machines with Oracles,Proc. 10th ICALP, Lecture Notes in Comp. Sci. 154 (1983), 573?584.","journal-title":"Proc. 10th ICALP, Lecture Notes in Comp. Sci."},{"key":"CR31","doi-asserted-by":"crossref","unstructured":"C. Papadimitriou, Games against Nature,Proc. 24th Ann. IEEE Symp. Foundations of Comp. Sci., 1983, 446?450.","DOI":"10.1109\/SFCS.1983.20"},{"key":"CR32","doi-asserted-by":"crossref","unstructured":"G. Peterson and J. Reif, Multiple-person alternation,Proc. 20th Ann. IEEE Symp. Foundations of Comp. Sci., 1979, 348?363.","DOI":"10.1109\/SFCS.1979.25"},{"key":"CR33","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1016\/0890-5401(89)90022-9","volume":"80","author":"M. Santha","year":"1989","unstructured":"M. Santha, Relativized Arthur-Merlin versus Merlin-Arthur games,Inf. and Computation 80 (1989), 44?49.","journal-title":"Inf. and Computation"},{"key":"CR34","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1145\/322047.322061","volume":"25","author":"J. Seiferas","year":"1978","unstructured":"J. Seiferas, M. Fischer, andA. Meyer, Separating Nondeterministic Time Complexity ClassesJ. Assoc. Comput. Mach. 25 (1978), 146?167.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR35","unstructured":"A. Shamir, IP=PSPACE, inProc. 31st Ann. IEEE Symp. Foundations of Comp. Sci., 1990, 11?15."},{"key":"CR36","unstructured":"J. Simon, On Some Central Problems in Computational Complexity, Ph.D. Thesis,Cornell University, Computer Science, Tech. Report TR 74-224, 1975."},{"key":"CR37","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J. T. Schwartz","year":"1980","unstructured":"J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities,J. Assoc. Comput. Mach. 27 (1980), 701?717.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR38","unstructured":"M. Szegedy, EfficientMIP protocol and a stronger condition on clique approximation, in preparation."},{"key":"CR39","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1109\/MAHC.1984.10036","volume":"6","author":"B. A. Trakhtenbrot","year":"1984","unstructured":"B. A. Trakhtenbrot, A survey of Russian approaches toPerebor (brute-force search) algorithms,Annals of the History of Computing 6 (1984), 384?400.","journal-title":"Annals of the History of Computing"},{"key":"CR40","doi-asserted-by":"crossref","unstructured":"S. Toda, On the computational power ofPP and ?P, inProc. 30th Ann. IEEE Symp. Foundations of Comp. Sci., 1989, 514?519.","DOI":"10.1109\/SFCS.1989.63527"},{"key":"CR41","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L. Valiant","year":"1979","unstructured":"L. Valiant, The complexity of computing the permanent,Theoretical Computer Science 8 (1979), 189?201.","journal-title":"Theoretical Computer Science"},{"key":"CR42","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"L. Valiant","year":"1986","unstructured":"L. Valiant, V. Vazirani,N P is as Easy as Detecting Unique Solutions,Theoretical Computer Science 47 (1986), 85?93.","journal-title":"Theoretical Computer Science"}],"container-title":["Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01200056.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01200056\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01200056","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T18:13:07Z","timestamp":1734977587000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01200056"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,3]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1991,3]]}},"alternative-id":["BF01200056"],"URL":"https:\/\/doi.org\/10.1007\/bf01200056","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,3]]}}}