{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T13:54:34Z","timestamp":1770818074587,"version":"3.50.1"},"reference-count":30,"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\/bf01200057","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T13:41:22Z","timestamp":1109252482000},"page":"41-66","source":"Crossref","is-referenced-by-count":54,"title":["Arithmetization: A new method in structural complexity theory"],"prefix":"10.1007","volume":"1","author":[{"given":"L\ufffdszl\ufffd","family":"Babai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lance","family":"Fortnow","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","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":"CR2","doi-asserted-by":"crossref","unstructured":"L. Babai, E-mail and the unexpected power of interaction, inProc. 5th Ann. IEEE Structures in Complexity Theory Conf., 1990, 30?44.","DOI":"10.1109\/SCT.1990.113952"},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"L. Babai and L. Fortnow, A characterization of #P by arithmetic straight line programs, inProc. 31st Ann. IEEE Symp. Foundations of Comp. Sci., 1990, 26?34.","DOI":"10.1109\/FSCS.1990.89521"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF01200056","volume":"1","author":"L. Babai","year":"1991","unstructured":"L. Babai, L. Fortnow, andC. Lund, Nondeterministic exponential time has two-prover interactive protocols,Computational Complexity 1 (1991), 3?40. Extended Abstract inProc. 31st Ann. IEEE Symp. Foundations of Comp. Sci., 1990, 16?25.","journal-title":"Computational Complexity"},{"key":"CR5","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,Journal Comp. Sys. Sci. 36 (1988), 254?276.","journal-title":"Journal Comp. Sys. Sci."},{"key":"CR6","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":"CR7","doi-asserted-by":"crossref","unstructured":"R. Beigel, J. Gill, and U. Hertrampf, Counting classes: thresholds, parity, mods, and fewness, inProc. 7th Symp. on Theoretical Aspects of Comp. Sci., Lecture Notes in Comp. Sci. 415 (1990), 49?57.","DOI":"10.1007\/3-540-52282-4_31"},{"key":"CR8","unstructured":"M. Blum, Designing programs that check their work, submitted toComm. of Assoc. Comput. Mach."},{"key":"CR9","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":"CR10","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":"CR11","doi-asserted-by":"crossref","unstructured":"R. Beigel, N. Reingold and D. Spielman, PP is Closed under Intersection, inProc. 23rd Ann. ACM Symp. Theory of Computing, 1991, to appear.","DOI":"10.1145\/103418.103426"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A. Chandra","year":"1981","unstructured":"A. Chandra, D. Kozen, andL. Stockmeyer, Alternation,J. Assoc. Comput. Mach 28 (1981), 114?133.","journal-title":"J. Assoc. Comput. Mach"},{"key":"CR13","unstructured":"J. Feigenbaum and L. Fortnow, On the random-self-reducibility of complete sets,University of Chicago Technical Report 90-22, 1990."},{"key":"CR14","unstructured":"S. Fenner, L. Fortnow, and S. Kurtz, Gap-definable counting classes,University of Chicago Technical Report 90-32, 1990."},{"key":"CR15","unstructured":"M. Garey and D. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Co., 1979"},{"key":"CR16","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":"CR17","unstructured":"S. Goldwasser and M. Sipser, Private coins versus public coins in interactive proof systems, inRandomness in Computation, S. Micali, ed.,Advances in Computing Research 5, JAI Press, 1989, 73?90."},{"key":"CR18","doi-asserted-by":"crossref","unstructured":"O. Goldreich, S. Micali, and A. Wigderson, Proofs that yield nothing but their validity and a methodology of cryptographic protocol design, inProc. 27th Ann. IEEE Symp. Foundations of Comp. Sci., 1986, 174?187.","DOI":"10.1109\/SFCS.1986.47"},{"key":"CR19","unstructured":"R. Lipton, New directions in testing, inProceedings of the DIMACS Workshop on Distributed Computing and Cryptography, 1989, to appear."},{"key":"CR20","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":"CR21","first-page":"598","volume":"41","author":"A. A. Razborov","year":"1981","unstructured":"A. A. Razborov, Lower bounds for the size of circuits of bounded depth with a complete basis including the logical addition function (in Russian),Matem. Zametki 41 (1981), 598?607. (English translation inMath. Notes of the Acad. Sci. USSR 41:4, 333?338.)","journal-title":"Matem. Zametki"},{"key":"CR22","doi-asserted-by":"crossref","unstructured":"U. Sch\u00f6ning, Probabilistic complexity classes and lowness, inProc. 2nd Ann. IEEE Structure in Complexity Theory Conf., 1987, 2?8.","DOI":"10.1109\/PSCT.1987.10319246"},{"key":"CR23","unstructured":"A. Shamir, IP=PSPACE, inProc. 31st Ann. IEEE Symp. Foundations of Comp. Sci., 1990, 11?15."},{"key":"CR24","doi-asserted-by":"crossref","unstructured":"R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, inProc. 19th Ann. ACM Symp. Theory of Computing, 1987, 77?82.","DOI":"10.1145\/28395.28404"},{"key":"CR25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. Stockmeyer","year":"1977","unstructured":"L. Stockmeyer, The Polynomial-time hierarchy,Theoretical Computer Science 3 (1977), 1?22.","journal-title":"Theoretical Computer Science"},{"key":"CR26","doi-asserted-by":"crossref","unstructured":"S. Toda, On the computational powel of PP and ?P, inProc. 30th Ann. IEEE Symp. Foundations of Comp. Sci, 1989, 514?519.","DOI":"10.1109\/SFCS.1989.63527"},{"key":"CR27","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":"CR28","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 andV. Vazirani, NP is as easy as detecting unique solutions,Theoretical Computer Science 47 (1986), 85?93.","journal-title":"Theoretical Computer Science"},{"key":"CR29","doi-asserted-by":"crossref","unstructured":"H. Venkateswaran, Circuit definitions of nondeterministic complexity classes, inProc. 8th FST & TCS, Lecture Notes in Comp. Sci 338 (1988), 175?192.","DOI":"10.1007\/3-540-50517-2_80"},{"key":"CR30","doi-asserted-by":"crossref","unstructured":"V. Zank\u00f3, #P-completeness via many-one reductions,Internat. J. of Foundat. Comp. Sci., to appear","DOI":"10.1142\/S0129054191000066"}],"container-title":["Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01200057.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01200057\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01200057","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T18:12:59Z","timestamp":1734977579000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01200057"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,3]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1991,3]]}},"alternative-id":["BF01200057"],"URL":"https:\/\/doi.org\/10.1007\/bf01200057","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,3]]}}}