{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T18:59:12Z","timestamp":1771700352797,"version":"3.50.1"},"reference-count":177,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":9873,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1987,3]]},"abstract":"<jats:p>One of the more significant achievements of twentieth century mathematics, especially from the viewpoints of logic and computer science, was the work of Church, G\u00f6del and Turing in the 1930's which provided a precise and robust definition of what it means for a problem to be computationally solvable, or decidable, and which showed that there are undecidable problems which arise naturally in logic and computer science. Indeed, when one is faced with a new computational problem, one of the first questions to be answered is whether the problem is decidable or undecidable. A problem is usually defined to be decidable if and only if it can be solved by some Turing machine, and the class of decidable problems defined in this way remains unchanged if \u201cTuring machine\u201d is replaced by any of a variety of other formal models of computation. The division of all problems into two classes, decidable or undecidable, is very coarse, and refinements have been made on both sides of the boundary. On the undecidable side, work in recursive function theory, using tools such as effective reducibility, has exposed much additional structure such as degrees of unsolvability. The main purpose of this survey article is to describe a branch of computational complexity theory which attempts to expose more structure within the decidable side of the boundary.<\/jats:p><jats:p>Motivated in part by practical considerations, the additional structure is obtained by placing upper bounds on the amounts of computational resources which are needed to solve the problem. Two common measures of the computational resources used by an algorithm are <jats:italic>time<\/jats:italic>, the number of steps executed by the algorithm, and <jats:italic>space<\/jats:italic>, the amount of memory used by the algorithm.<\/jats:p>","DOI":"10.2307\/2273858","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T22:20:33Z","timestamp":1146954033000},"page":"1-43","source":"Crossref","is-referenced-by-count":51,"title":["Classifying the computational complexity of problems"],"prefix":"10.1017","volume":"52","author":[{"given":"Larry","family":"Stockmeyer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200029959_bib131","volume-title":"Degree of difficulty of computing a function and a partial ordering of recursive sets","author":"Rabin","year":"1960"},{"key":"S0022481200029959_bib013","doi-asserted-by":"publisher","DOI":"10.1145\/321637.321648"},{"key":"S0022481200029959_bib067","doi-asserted-by":"publisher","DOI":"10.1109\/MAHC.1981.10005"},{"key":"S0022481200029959_bib087","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(75)80050-X"},{"key":"S0022481200029959_bib104","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90027-6"},{"key":"S0022481200029959_bib166","doi-asserted-by":"publisher","DOI":"10.1137\/0208013"},{"key":"S0022481200029959_bib177","first-page":"1","volume-title":"Proceedings of the 26th IEEE Symposium on Foundations of Computer Science","author":"Yao","year":"1985"},{"key":"S0022481200029959_bib034","doi-asserted-by":"publisher","DOI":"10.1137\/0205040"},{"key":"S0022481200029959_bib110","doi-asserted-by":"publisher","DOI":"10.1145\/322261.322271"},{"key":"S0022481200029959_bib033","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80029-7"},{"key":"S0022481200029959_bib140","doi-asserted-by":"publisher","DOI":"10.1145\/322290.322306"},{"key":"S0022481200029959_bib124","first-page":"307","volume-title":"Proceedings of the 20th IEEE Symposium on Foundations of Computer Science","author":"Pippenger","year":"1979"},{"key":"S0022481200029959_bib109","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90002-2"},{"key":"S0022481200029959_bib095","first-page":"164","volume-title":"Proceedings of the 9th ACM Symposium on Theory of Computing","author":"Kozen","year":"1977"},{"key":"S0022481200029959_bib132","first-page":"58","volume-title":"Proceedings of the 1964 international congress for logic, methodology and philosophy of science","author":"Rabin","year":"1965"},{"key":"S0022481200029959_bib070","first-page":"6","volume-title":"Proceedings of the 18th ACM Symposium on Theory of Computing","author":"Hastad","year":"1986"},{"key":"S0022481200029959_bib049","first-page":"114","volume-title":"Proceedings of the 10th ACM Symposium on Theory of Computing","author":"Fortune","year":"1978"},{"key":"S0022481200029959_bib108","first-page":"271","volume-title":"Proceedings of the 22nd IEEE Symposium on Foundations of Computer Science","author":"Mahaney","year":"1981"},{"key":"S0022481200029959_bib046","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0062837"},{"key":"S0022481200029959_bib082","volume-title":"The polynomial hierarchy and a simple model for competitive analysis","author":"Jeroslow","year":"1983"},{"key":"S0022481200029959_bib047","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90046-1"},{"key":"S0022481200029959_bib141","first-page":"320","article-title":"Presburger arithmetic with bounded quantifier alternation","author":"Reddy","year":"1978","journal-title":"Proceedings of the 10th ACM Symposium on Theory of Computing"},{"key":"S0022481200029959_bib107","doi-asserted-by":"publisher","DOI":"10.1145\/321892.321895"},{"key":"S0022481200029959_bib128","first-page":"109","volume-title":"Proceedings of the 17th IEEE Symposium on Foundations of Computer Science","author":"Pratt","year":"1976"},{"key":"S0022481200029959_bib003","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19550010403"},{"key":"S0022481200029959_bib079","doi-asserted-by":"publisher","DOI":"10.1145\/322358.322373"},{"key":"S0022481200029959_bib002","first-page":"51","volume-title":"Proceedings of the 26th IEEE Symposium on Foundations of Computer Science","author":"Ambos-Spies","year":"1985"},{"key":"S0022481200029959_bib143","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288964"},{"key":"S0022481200029959_bib121","first-page":"74","volume-title":"Proceedings of the 26th IEEE Symposium on Foundations of Computer Science","author":"Papadimitriou","year":"1985"},{"key":"S0022481200029959_bib051","unstructured":"F\u00fcrer, M. , Nicht-elementare untere Schranken in der Automaten-theorie, Doctoral Thesis, ETH, Z\u00fcrich, 1978."},{"key":"S0022481200029959_bib030","first-page":"99","volume-title":"L'Enseignement Math\u00e9matique","volume":"27","author":"Cook","year":"1981"},{"key":"S0022481200029959_bib019","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19600060105"},{"key":"S0022481200029959_bib169","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970265"},{"key":"S0022481200029959_bib160","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3837"},{"key":"S0022481200029959_bib171","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"S0022481200029959_bib018","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90036-5"},{"key":"S0022481200029959_bib059","first-page":"59","volume-title":"Proceedings of the 18th ACM Symposium on Theory of Computing","author":"Goldwasser","year":"1986"},{"key":"S0022481200029959_bib127","first-page":"46","volume-title":"Proceedings of the 18th IEEE Symposium on Foundations of Computer Science","author":"Pnueli","year":"1977"},{"key":"S0022481200029959_bib025","unstructured":"Compton, K. and Henson, C. W. , A new method for proving lower bounds on the computational complexity of first-order theories, manuscript in preparation. 1984."},{"key":"S0022481200029959_bib112","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0064872"},{"key":"S0022481200029959_bib038","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(84)90022-0"},{"key":"S0022481200029959_bib172","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"S0022481200029959_bib064","first-page":"480","volume-title":"Proceedings of the international joint conference on artificial intelligence","author":"Halpern","year":"1985"},{"key":"S0022481200029959_bib069","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1965-0170805-7"},{"key":"S0022481200029959_bib058","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90092-5"},{"key":"S0022481200029959_bib081","first-page":"347","volume-title":"Proceedings of the 15th ACM Symposium on Theory of Computing","author":"Immerman","year":"1983"},{"key":"S0022481200029959_bib098","doi-asserted-by":"publisher","DOI":"10.1145\/990518.990519"},{"key":"S0022481200029959_bib105","first-page":"27","volume-title":"Nauchno-Tekhnicheskaya Informatsiya","author":"Livchak","year":"1983"},{"key":"S0022481200029959_bib041","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1961-0139530-9"},{"key":"S0022481200029959_bib092","doi-asserted-by":"publisher","DOI":"10.1145\/5657.5658"},{"key":"S0022481200029959_bib126","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90010-2"},{"key":"S0022481200029959_bib091","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"S0022481200029959_bib101","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90007-8"},{"key":"S0022481200029959_bib100","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(75)90016-X"},{"key":"S0022481200029959_bib103","first-page":"115","article-title":"Universal sorting problems","volume":"9","author":"Levin","year":"1973","journal-title":"Problemy Peredachi Informatsii"},{"key":"S0022481200029959_bib026","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-16486-3_95"},{"key":"S0022481200029959_bib063","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90008-6"},{"key":"S0022481200029959_bib021","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322243"},{"key":"S0022481200029959_bib123","first-page":"429","volume-title":"Proceedings of the 24th IEEE Symposium on Foundations of Computer Science","author":"Paul","year":"1983"},{"key":"S0022481200029959_bib035","volume-title":"The undecidable","author":"Davis","year":"1965"},{"key":"S0022481200029959_bib053","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"},{"key":"S0022481200029959_bib167","first-page":"1","volume-title":"Proceedings of the 5th ACM Symposium on Theory of Computing","author":"Stockmeyer","year":"1973"},{"key":"S0022481200029959_bib028","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80028-5"},{"key":"S0022481200029959_bib096","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90048-1"},{"key":"S0022481200029959_bib153","first-page":"160","volume":"17","author":"Scholz","year":"1952","journal-title":"Ein ungel\u00f6stes Problem in der symbolischen Logik"},{"key":"S0022481200029959_bib115","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80043-8"},{"key":"S0022481200029959_bib144","first-page":"161","volume-title":"Proceedings of the 6th ACM Symposium on Theory of Computing","author":"Robertson","year":"1974"},{"key":"S0022481200029959_bib083","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(83)90019-6"},{"key":"S0022481200029959_bib155","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(77)80042-1"},{"key":"S0022481200029959_bib088","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90068-2"},{"key":"S0022481200029959_bib150","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80006-X"},{"key":"S0022481200029959_bib161","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0015772"},{"key":"S0022481200029959_bib080","first-page":"147","volume-title":"Proceedings of the 14th ACM Symposium on Theory of Computing","author":"Immerman","year":"1982"},{"key":"S0022481200029959_bib129","first-page":"115","volume-title":"Proceedings of the 20th IEEE Symposium on Foundations of Computer Science","author":"Pratt","year":"1979"},{"key":"S0022481200029959_bib077","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(84)90092-6"},{"key":"S0022481200029959_bib094","first-page":"1093","article-title":"A polynomial algorithm for linear programming","volume":"244","author":"Khachiyan","year":"1979","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S0022481200029959_bib176","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90062-1"},{"key":"S0022481200029959_bib075","doi-asserted-by":"publisher","DOI":"10.1137\/0207007"},{"key":"S0022481200029959_bib114","first-page":"125","volume-title":"Proceedings of the 13th IEEE Symposium on Switching and Automata Theory","author":"Meyer","year":"1972"},{"key":"S0022481200029959_bib090","first-page":"139","volume":"39","author":"Jones","year":"1974","journal-title":"Turing machines and the spectra of first-order formulas"},{"key":"S0022481200029959_bib044","unstructured":"Ferrante, J. , Some upper and lower bounds on decision procedures in logic, Doctoral Thesis, Department of Mathematics, M.I.T., Cambridge, Massachusetts, 1974; also Report TR-139, M.I.T. Laboratory for Computer Science."},{"key":"S0022481200029959_bib133","first-page":"1","article-title":"Decidability of second-order theories and automata on infinite trees","volume":"141","author":"Rabin","year":"1969","journal-title":"Transactions of the American Mathematical Society"},{"key":"S0022481200029959_bib006","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90029-2"},{"key":"S0022481200029959_bib116","unstructured":"Monk, L. , Elementary recursive decision procedures, Ph.D. Thesis, University of California, Berkeley, California, 1975."},{"key":"S0022481200029959_bib084","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90032-4"},{"key":"S0022481200029959_bib134","first-page":"615","volume-title":"Information Processing 74","author":"Rabin","year":"1974"},{"key":"S0022481200029959_bib076","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80038-4"},{"key":"S0022481200029959_bib158","first-page":"61","volume-title":"Proceedings of the 15th ACM Symposium on Theory of Computing","author":"Sipser","year":"1983"},{"key":"S0022481200029959_bib152","doi-asserted-by":"publisher","DOI":"10.1007\/BF00265223"},{"key":"S0022481200029959_bib102","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90044-3"},{"key":"S0022481200029959_bib015","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90057-8"},{"key":"S0022481200029959_bib054","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"Garey","year":"1979"},{"key":"S0022481200029959_bib071","volume-title":"A compendium of problems complete for P","author":"Hoover"},{"key":"S0022481200029959_bib163","first-page":"179","volume-title":"Proceedings of the 6th IEEE Symposium on Switching Circuit Theory and Logical Design","author":"Stearns","year":"1965"},{"key":"S0022481200029959_bib055","doi-asserted-by":"publisher","DOI":"10.1137\/0206049"},{"key":"S0022481200029959_bib093","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(69)80011-5"},{"key":"S0022481200029959_bib057","doi-asserted-by":"publisher","DOI":"10.1145\/322344.322353"},{"key":"S0022481200029959_bib072","doi-asserted-by":"publisher","DOI":"10.1145\/322003.322015"},{"key":"S0022481200029959_bib113","first-page":"477","volume-title":"Proceedings of the International Congress of Mathematicians (Vancouver, 1974)","volume":"2","author":"Meyer","year":"1975"},{"key":"S0022481200029959_bib010","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90037-7"},{"key":"S0022481200029959_bib045","doi-asserted-by":"publisher","DOI":"10.1137\/0204006"},{"key":"S0022481200029959_bib056","doi-asserted-by":"publisher","DOI":"10.1145\/1008354.1008356"},{"key":"S0022481200029959_bib106","unstructured":"Lo, L. , On the computational complexity of the theory of abelian groups, Ph.D. Thesis, University of Michigan, Ann Arbor, Michigan, 1984."},{"key":"S0022481200029959_bib062","volume-title":"Logic and the challenge of computer science","author":"Gurevich","year":"1985"},{"key":"S0022481200029959_bib118","doi-asserted-by":"publisher","DOI":"10.1145\/62.322435"},{"key":"S0022481200029959_bib099","doi-asserted-by":"publisher","DOI":"10.1137\/0206033"},{"key":"S0022481200029959_bib174","first-page":"137","volume-title":"Proceedings of the 14th ACM Symposium on Theory of Computing","author":"Vardi","year":"1982"},{"key":"S0022481200029959_bib061","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0099486"},{"key":"S0022481200029959_bib164","unstructured":"Stockmeyer, L. J. , The complexity of decision problems in automata theory and logic, Doctoral Thesis, Department of Electrical Engineering, M.I.T., Cambridge, Massachusetts, 1974; also Report TR-133, M.I.T. Laboratory for Computer Science."},{"key":"S0022481200029959_bib162","doi-asserted-by":"publisher","DOI":"10.1137\/0206006"},{"key":"S0022481200029959_bib023","first-page":"24","volume-title":"Proceedings of the 1964 international congress for logic, methodology and philosophy of science","author":"Cobham","year":"1965"},{"key":"S0022481200029959_bib145","doi-asserted-by":"publisher","DOI":"10.1137\/0213018"},{"key":"S0022481200029959_bib117","volume-title":"Elementary induction on abstract structures","author":"Moschovakis","year":"1974"},{"key":"S0022481200029959_bib149","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322221"},{"key":"S0022481200029959_bib139","first-page":"561","volume":"41","author":"Rackoff","year":"1976","journal-title":"On the complexity of the theories of weak direct powers"},{"key":"S0022481200029959_bib151","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(78)90045-4"},{"key":"S0022481200029959_bib122","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90068-0"},{"key":"S0022481200029959_bib007","doi-asserted-by":"publisher","DOI":"10.1137\/0210008"},{"key":"S0022481200029959_bib135","doi-asserted-by":"publisher","DOI":"10.1016\/0022-314X(80)90084-0"},{"key":"S0022481200029959_bib001","volume-title":"The design and analysis of computer algorithms","author":"Aho","year":"1974"},{"key":"S0022481200029959_bib073","volume-title":"Introduction to automata theory, languages, and computation","author":"Hopcroft","year":"1979"},{"key":"S0022481200029959_bib031","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80041-3"},{"key":"S0022481200029959_bib032","doi-asserted-by":"publisher","DOI":"10.1145\/358141.358144"},{"key":"S0022481200029959_bib170","doi-asserted-by":"publisher","DOI":"10.1525\/9780520348097"},{"key":"S0022481200029959_bib020","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90012-5"},{"key":"S0022481200029959_bib159","first-page":"330","volume-title":"Proceedings of the 15th ACM Symposium on Theory of Computing","author":"Sipser","year":"1983"},{"key":"S0022481200029959_bib004","first-page":"421","volume-title":"Proceedings of the 17th ACM Symposium on Theory of Computing","author":"Babai","year":"1985"},{"key":"S0022481200029959_bib039","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"S0022481200029959_bib138","volume-title":"The complexity of theories of the monadic predicate calculus","author":"Rackoff","year":"1975"},{"key":"S0022481200029959_bib052","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90115-3"},{"key":"S0022481200029959_bib066","first-page":"304","volume-title":"Proceedings of the 18th ACM Symposium on Theory of Computing","author":"Halpern","year":"1986"},{"key":"S0022481200029959_bib089","doi-asserted-by":"publisher","DOI":"10.1007\/BF01683259"},{"key":"S0022481200029959_bib040","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(75)80060-2"},{"key":"S0022481200029959_bib024","first-page":"134","volume-title":"Second GI conference on automata theory and format languages","volume":"33","author":"Collins","year":"1975"},{"key":"S0022481200029959_bib068","first-page":"40","volume-title":"Proceedings of the 9th symposium on mathematical foundations of computer science","volume":"88","author":"Hartmanis","year":"1980"},{"key":"S0022481200029959_bib175","first-page":"240","volume-title":"Proceedings of the 17th ACM Symposium on Theory of Computing","author":"Vardi","year":"1985"},{"key":"S0022481200029959_bib086","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(85)90046-X"},{"key":"S0022481200029959_bib120","volume-title":"Combinatorial optimization: algorithms and complexity","author":"Papadimitriou","year":"1982"},{"key":"S0022481200029959_bib005","doi-asserted-by":"publisher","DOI":"10.1137\/0204037"},{"key":"S0022481200029959_bib014","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90041-8"},{"key":"S0022481200029959_bib146","first-page":"413","volume-title":"Information Processing 83 (Proceedings of the ninth IFIP world computer congress, Paris, 1983","author":"Robson","year":"1983"},{"key":"S0022481200029959_bib165","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90061-X"},{"key":"S0022481200029959_bib148","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90038-6"},{"key":"S0022481200029959_bib012","doi-asserted-by":"publisher","DOI":"10.1145\/321386.321395"},{"key":"S0022481200029959_bib085","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90022-1"},{"key":"S0022481200029959_bib011","doi-asserted-by":"publisher","DOI":"10.1137\/0206023"},{"key":"S0022481200029959_bib017","doi-asserted-by":"publisher","DOI":"10.1137\/0206054"},{"key":"S0022481200029959_bib156","doi-asserted-by":"publisher","DOI":"10.1145\/322047.322061"},{"key":"S0022481200029959_bib125","doi-asserted-by":"publisher","DOI":"10.1145\/322123.322138"},{"key":"S0022481200029959_bib157","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0012797"},{"key":"S0022481200029959_bib060","first-page":"210","volume-title":"Proceedings of the 24th IEEE Symposium on Foundations of Computer Science","author":"Gurevich","year":"1983"},{"key":"S0022481200029959_bib043","first-page":"43","volume-title":"Complexity of computation","volume":"7","author":"Fagin","year":"1974"},{"key":"S0022481200029959_bib142","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90034-5"},{"key":"S0022481200029959_bib173","first-page":"458","volume-title":"Proceedings of the 17th ACM Symposium on Theory of Computing","author":"Valiant","year":"1985"},{"key":"S0022481200029959_bib009","first-page":"76","volume-title":"Proceedings of the 17th IEEE Symposium on Foundations of Computer Science","author":"Berman","year":"1976"},{"key":"S0022481200029959_bib036","first-page":"748","article-title":"On the impossibility of eliminating complete enumeration in computing a function relative to its graph","volume":"189","author":"Dekhtiar","year":"1969","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S0022481200029959_bib074","doi-asserted-by":"publisher","DOI":"10.1145\/322017.322020"},{"key":"S0022481200029959_bib037","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90152-2"},{"key":"S0022481200029959_bib048","first-page":"27","volume-title":"Complexity of computation","volume":"7","author":"Fischer","year":"1974"},{"key":"S0022481200029959_bib119","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90045-5"},{"key":"S0022481200029959_bib008","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1970-0276200-X"},{"key":"S0022481200029959_bib130","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80037-2"},{"key":"S0022481200029959_bib065","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90097-X"},{"key":"S0022481200029959_bib029","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80046-2"},{"key":"S0022481200029959_bib111","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(82)90048-2"},{"key":"S0022481200029959_bib154","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"S0022481200029959_bib097","doi-asserted-by":"publisher","DOI":"10.1145\/321864.321877"},{"key":"S0022481200029959_bib147","volume-title":"Theory of recursive functions and effective computability","author":"Rogers","year":"1967"},{"key":"S0022481200029959_bib168","doi-asserted-by":"publisher","DOI":"10.1145\/321906.321913"},{"key":"S0022481200029959_bib136","doi-asserted-by":"publisher","DOI":"10.1137\/0209024"},{"key":"S0022481200029959_bib027","first-page":"151","volume-title":"Proceedings of the 3rd ACM Symposium on Theory of Computing","author":"Cook","year":"1971"},{"key":"S0022481200029959_bib050","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(81)90016-9"},{"key":"S0022481200029959_bib042","doi-asserted-by":"publisher","DOI":"10.1145\/2455.214111"},{"key":"S0022481200029959_bib022","first-page":"98","volume-title":"Proceedings of the 17th IEEE Symposium on Foundations of Computer Science","author":"Chandra","year":"1976"},{"key":"S0022481200029959_bib016","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-13331-3_50"},{"key":"S0022481200029959_bib078","doi-asserted-by":"publisher","DOI":"10.1145\/321724.321727"},{"key":"S0022481200029959_bib137","unstructured":"Rackoff, C. W. , The computational complexity of some logical theories, Doctoral Thesis, Department of Electrical Engineering, M.I.T., Cambridge, Massachusetts, 1974; also Report TR-144, M.I.T. Laboratory for Computer Science."}],"container-title":["The Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200029959","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,11]],"date-time":"2022-04-11T08:13:56Z","timestamp":1649664836000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.cambridge.org\/core\/product\/identifier\/S0022481200029959\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,3]]},"references-count":177,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1987,3]]}},"alternative-id":["S0022481200029959"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.2307\/2273858","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1987,3]]}}}