{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T16:18:00Z","timestamp":1779121080726,"version":"3.51.4"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1988,11,1]],"date-time":"1988-11-01T00:00:00Z","timestamp":594345600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Philos Logic"],"published-print":{"date-parts":[[1988,11]]},"DOI":"10.1007\/bf00297511","type":"journal-article","created":{"date-parts":[[2004,10,6]],"date-time":"2004-10-06T11:42:28Z","timestamp":1097062948000},"page":"355-389","source":"Crossref","is-referenced-by-count":94,"title":["Logic and the complexity of reasoning"],"prefix":"10.1007","volume":"17","author":[{"given":"Hector J.","family":"Levesque","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","volume-title":"Entailment: The Logic of Relevance and Necessity","author":"A. Anderson","year":"1975","unstructured":"Anderson, A. and Belnap, N.: 1975, Entailment: The Logic of Relevance and Necessity. Princeton University Press, Princeton, NJ."},{"issue":"1","key":"CR2","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1017\/S0140525X00021555","volume":"9","author":"D. Ballard","year":"1986","unstructured":"Ballard, D.: 1986. Cortical connections and parallel processing: structure and function. The Behavioral and Brain Sciences 9(1) 67?90.","journal-title":"The Behavioral and Brain Sciences"},{"key":"CR3","volume-title":"Computational Complexity and Natural Language","author":"G. E. Barton","year":"1987","unstructured":"Barton, G. E., Berwick, R. and Ristad, E.: 1987, Computational Complexity and Natural Language. MIT Press, Cambridge, MA."},{"issue":"10","key":"CR4","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1109\/MC.1983.1654194","volume":"16","author":"R. Brachman","year":"1983","unstructured":"Brachman, R.: 1983, What is-a is and isn't: an analysis of taxonomic links in semantic networks. IEEE Computer 16(10): 30?36.","journal-title":"IEEE Computer"},{"key":"CR5","unstructured":"Brachman, R. and Levesque, H.: 1984, The tractability of subsumption in frame-based description languages. In AAAI-84, pages 34?37, Austin, TX."},{"key":"CR6","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/BF00278382","volume":"11","author":"G. Carlson","year":"1982","unstructured":"Carlson, G.: 1982, Generic terms and generic sentences. Journal of Philosophical Logic 11: 145?182.","journal-title":"Journal of Philosophical Logic"},{"key":"CR7","volume-title":"Minimal Rationality","author":"C. Cherniak","year":"1986","unstructured":"Cherniak, C.: 1986, Minimal Rationality. Bradford Books, Cambridge, MA."},{"key":"CR8","doi-asserted-by":"crossref","first-page":"40","DOI":"10.2307\/2269326","volume":"1","author":"A. Church","year":"1936","unstructured":"Church, A.: 1936, A note on the Entscheidungsproblem. The Journal of Symbolic Logic 1: 40?41.","journal-title":"The Journal of Symbolic Logic"},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"Cooks, S.: 1971, The complexity of theorem proving procedures. In The 3rd. Annual Symposium on the Theory of Computing, pages 151?158, New York, NY.","DOI":"10.1145\/800157.805047"},{"key":"CR10","unstructured":"de Kleer, J. and Brown, J. S.: 1983, The origin, form, and logic of qualitative physical laws. In IJCAI-83, pages 1158?1169, Karlsruhe, West Germany."},{"key":"CR11","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0743-1066(84)90014-1","volume":"3","author":"W. Dowling","year":"1984","unstructured":"Dowling, W. and Gallier, J.: 1984, Linear-time algorithms for testing the satisfiability of propositional horn formulae. The Journal of Logic Programming 3: 267?284.","journal-title":"The Journal of Logic Programming"},{"key":"CR12","volume-title":"Mind over Machines","author":"H. Dreyfus","year":"1986","unstructured":"Dreyfus, H. and Dreyfus, S.: 1986, Mind over Machines. Macmillan, New York, NY."},{"key":"CR13","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1007\/BF00373152","volume":"29","author":"M. Dunn","year":"1976","unstructured":"Dunn, M.: 1976, Intuitive semantics for first-degree entailments and ?coupled trees?. Philosophical Studies 29: 149?168.","journal-title":"Philosophical Studies"},{"key":"CR14","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M. and Johnson, D.: 1979, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco, CA."},{"key":"CR15","unstructured":"Genesereth, M.: 1983, An overview of meta-level architecture. In AAAI-83, pages 119?124, Washington, D.C."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/0304-3975(85)90144-6","volume":"39","author":"A. Haken","year":"1985","unstructured":"Haken, A.: 1985, The intractability of resolution. Theoretical Computer Science 39: 297?308.","journal-title":"Theoretical Computer Science"},{"key":"CR17","volume-title":"Algorithmics: The Spirit of Computing","author":"D. Harel","year":"1986","unstructured":"Harel, D.: 1986, Algorithmics: The Spirit of Computing. Addison-Wesley, Don Mills, Ontario."},{"issue":"3","key":"CR18","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1111\/j.1467-8640.1987.tb00192.x","volume":"3","author":"P. Hayes","year":"1987","unstructured":"Hayes, P.: 1987, A critique of pure treason. Computational Intelligence 3(3): 179?185.","journal-title":"Computational Intelligence"},{"key":"CR19","volume-title":"Introduction to Expert Systems","author":"P. Jackson","year":"1986","unstructured":"Jackson, P.: 1986, Introduction to Expert Systems. Addison-Wesley, Don Mills, Ontario."},{"key":"CR20","volume-title":"Mental Models","author":"P. Johnson-Laird","year":"1983","unstructured":"Johnson-Laird, P.: 1983, Mental Models. Harvard University Press, Cambridge, MA."},{"key":"CR21","doi-asserted-by":"crossref","unstructured":"Kirousis, L. and Papadimitriou, C.: 1985, The complexity of recognizing polyhedral scenes. In The 26th Annual Symposium on the Foundations of Computer Science, Portland, Oregon.","DOI":"10.1109\/SFCS.1985.59"},{"key":"CR22","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/0004-3702(71)90012-9","volume":"2","author":"R. Kowalski","year":"1971","unstructured":"Kowalski, R. and Kuehner, D.: 1971, Linear resolution with selection functions. Artificial Intelligence 2: 227?260.","journal-title":"Artificial Intelligence"},{"key":"CR23","unstructured":"Kramer, B.: 1984, Representing control strategies using reflection. In CSCSI-84, pages 153?158, London, Ontario."},{"issue":"1","key":"CR24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0004-3702(87)90050-6","volume":"33","author":"J. E. Laird","year":"1987","unstructured":"Laird, J. E., Newell, A., and Rosenbloom, P. S.: 1987, Soar: an architecture for general intelligence. Artificial Intelligence 33(1): 1?64.","journal-title":"Artificial Intelligence"},{"key":"CR25","unstructured":"Levesque, H.: 1984, A logic of implicit and explicit belief. In AAAI-84, pages 198?202, Austin, TX."},{"issue":"1","key":"CR26","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0004-3702(86)90068-8","volume":"30","author":"H. Levesque","year":"1986","unstructured":"Levesque, H.: 1986a, Making believers out of computers. Artificial Intelligence 30(1): 81?108.","journal-title":"Artificial Intelligence"},{"key":"CR27","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1146\/annurev.cs.01.060186.001351","volume":"1","author":"H. Levesque","year":"1986","unstructured":"Levesque, H.: 1986b, Knowledge representation and reasoning. Annual Reviews of Computer Science 1: 255?287.","journal-title":"Annual Reviews of Computer Science"},{"issue":"3","key":"CR28","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1111\/j.1467-8640.1987.tb00182.x","volume":"3","author":"H. Levesque","year":"1987","unstructured":"Levesque, H.: 1987, Taking issue: guest editor's introduction. Computational Intelligence 3(3): 149?150.","journal-title":"Computational Intelligence"},{"key":"CR29","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1146\/annurev.cs.02.060187.001003","volume":"2","author":"N. Megiddo","year":"1987","unstructured":"Megiddo, N.: 1987, Linear programming (1986). Annual Reviews of Computer Science 2: 119?145.","journal-title":"Annual Reviews of Computer Science"},{"key":"CR30","unstructured":"Moore, R.: 1982, The role of logic in knowledge representation and commonsense reasoning. In AAAI-82, pages 428?433, Pittsburgh, PA."},{"issue":"1","key":"CR31","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0004-3702(82)90012-1","volume":"18","author":"A. Newell","year":"1982","unstructured":"Newell, A.: 1982, The knowledge level. Artificial Intelligence 18(1): 87?127.","journal-title":"Artificial Intelligence"},{"key":"CR32","unstructured":"Patel-Schneider, P.: 1985, A decidable first-order logic for knowledge representation. In IJCAI-85, pages 455?458, Los Angeles, CA."},{"key":"CR33","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/2004.001.0001","volume-title":"Computation and Cognition: Towards a Foundation for Cognitive Science","author":"Z. Pylyshyn","year":"1984","unstructured":"Pylyshyn, Z.: 1984, Computation and Cognition: Towards a Foundation for Cognitive Science. Bradford Books, Cambridge, MA."},{"key":"CR34","first-page":"55","volume-title":"Logic and Databases","author":"R. Reiter","year":"1978","unstructured":"Reiter, R.: 1978, On closed world databases. In Gallaire, H. and Minker, J., editors, Logic and Databases, pages 55?76, Plenum Press, New York, NY."},{"key":"CR35","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1146\/annurev.cs.02.060187.001051","volume":"2","author":"R. Reiter","year":"1987","unstructured":"Reiter, R.: 1987, Nonmonotonic reasoning. Annual Reviews of Computer Science 2: 147?186.","journal-title":"Annual Reviews of Computer Science"},{"key":"CR36","volume-title":"Parallel Distributed Processing","year":"1986","unstructured":"Rumelhart, D. and McClelland, J. (editors): 1986, Parallel Distributed Processing. MIT Press, Cambridge, MA."},{"key":"CR37","doi-asserted-by":"crossref","unstructured":"Selman, B. and Kautz, H.: 1988, The complexity of model-preference default theories. In CSCSI-88, Edmonton, Alberta.","DOI":"10.1007\/3-540-50701-9_23"},{"key":"CR38","volume-title":"The Sciences of the Artificial","author":"H. Simon","year":"1969","unstructured":"Simon, H.: 1969. The Sciences of the Artificial. MIT Press, Cambridge, MA."},{"key":"CR39","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/BF00133569","volume":"4","author":"J. Tsotsos","year":"1988","unstructured":"Tsotsos, J.: 1988, A complexity level analysis of immediate vision. International Journal of Computer Vision 4: 303?320.","journal-title":"International Journal of Computer Vision"},{"key":"CR40","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"L. Valiant","year":"1986","unstructured":"Valiant, L. and Vazirani, V.: 1986, NP is as easy as detecting unique solutions. Theoretical Computer Science 47: 85?93.","journal-title":"Theoretical Computer Science"}],"container-title":["Journal of Philosophical Logic"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00297511.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF00297511\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00297511","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,18]],"date-time":"2024-12-18T22:14:36Z","timestamp":1734560076000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF00297511"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,11]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1988,11]]}},"alternative-id":["BF00297511"],"URL":"https:\/\/doi.org\/10.1007\/bf00297511","relation":{},"ISSN":["0022-3611","1573-0433"],"issn-type":[{"value":"0022-3611","type":"print"},{"value":"1573-0433","type":"electronic"}],"subject":[],"published":{"date-parts":[[1988,11]]}}}