{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T11:00:55Z","timestamp":1775818855302,"version":"3.50.1"},"reference-count":129,"publisher":"Wiley","issue":"6","license":[{"start":{"date-parts":[[2008,9,1]],"date-time":"2008-09-01T00:00:00Z","timestamp":1220227200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Cognitive Science"],"published-print":{"date-parts":[[2008,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The recognition that human minds\/brains are finite systems with limited resources for computation has led some researchers to advance the <jats:italic>Tractable Cognition thesis<\/jats:italic>: Human cognitive capacities are constrained by computational tractability. This thesis, if true, serves cognitive psychology by constraining the space of computational\u2010level theories of cognition. To utilize this constraint, a precise and workable definition of \u201ccomputational tractability\u201d is needed. Following computer science tradition, many cognitive scientists and psychologists define computational tractability as polynomial\u2010time computability, leading to the <jats:italic>P\u2010Cognition thesis<\/jats:italic>. This article explains how and why the P\u2010Cognition thesis may be overly restrictive, risking the exclusion of veridical computational\u2010level theories from scientific investigation. An argument is made to replace the P\u2010Cognition thesis by the <jats:italic>FPT\u2010Cognition thesis<\/jats:italic> as an alternative formalization of the Tractable Cognition thesis (here, FPT stands for fixed\u2010parameter tractable). Possible objections to the Tractable Cognition thesis, and its proposed formalization, are discussed, and existing misconceptions are clarified.<\/jats:p>","DOI":"10.1080\/03640210801897856","type":"journal-article","created":{"date-parts":[[2008,8,14]],"date-time":"2008-08-14T05:27:17Z","timestamp":1218691637000},"page":"939-984","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":180,"title":["The Tractable Cognition Thesis"],"prefix":"10.1111","volume":"32","author":[{"given":"Iris","family":"Van Rooij","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2008,9]]},"reference":[{"key":"e_1_2_11_2_1","doi-asserted-by":"publisher","DOI":"10.1037\/0033-295X.85.4.249"},{"key":"e_1_2_11_3_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0140525X00023554"},{"key":"e_1_2_11_4_1","volume-title":"The adaptive character of thought","author":"Anderson J. R.","year":"1990"},{"key":"e_1_2_11_5_1","doi-asserted-by":"crossref","volume-title":"Computational complexity: A modern approach","author":"Arora S.","DOI":"10.1017\/CBO9780511804090"},{"key":"e_1_2_11_6_1","volume-title":"Computational complexity and natural language","author":"Barton G. E.","year":"1987"},{"key":"e_1_2_11_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)90081-7"},{"key":"e_1_2_11_8_1","volume-title":"A computational foundation for the study of cognition (Tech. Rep. in Philosophy\u2010Neuroscience\u2010Psychology.)","author":"Chalmers D. J.","year":"1994"},{"key":"e_1_2_11_9_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1005272027245"},{"issue":"7","key":"e_1_2_11_10_1","article-title":"Special issue: Probabilistic models in cognition. [Special issue]","volume":"10","author":"Chater N.","year":"2006","journal-title":"Trends in Cognitive Sciences"},{"key":"e_1_2_11_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-2496(03)00013-0"},{"key":"e_1_2_11_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1364-6613(02)00005-0"},{"key":"e_1_2_11_13_1","volume-title":"Minimal rationality","author":"Cherniak C.","year":"1986"},{"key":"e_1_2_11_14_1","doi-asserted-by":"publisher","DOI":"10.2307\/2371045"},{"key":"e_1_2_11_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00976283"},{"key":"e_1_2_11_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00974187"},{"key":"e_1_2_11_17_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxl062"},{"key":"e_1_2_11_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"e_1_2_11_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(90)90060-D"},{"key":"e_1_2_11_20_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015607401307"},{"key":"e_1_2_11_21_1","doi-asserted-by":"crossref","first-page":"117","DOI":"10.7551\/mitpress\/2930.003.0009","volume-title":"Explanation and cognition","author":"Cummins R.","year":"2000"},{"key":"e_1_2_11_22_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1985.0070"},{"key":"e_1_2_11_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_11_24_1","doi-asserted-by":"publisher","DOI":"10.7771\/1932-6246.1004"},{"issue":"1","key":"e_1_2_11_25_1","first-page":"19","article-title":"Complexity results for agent design problems","volume":"1","author":"Dunne P. E.","year":"2003","journal-title":"Annals of Mathematics, Computing & Teleinformatics"},{"key":"e_1_2_11_26_1","first-page":"147","article-title":"Is the brain analog or digital? The solution and its consequences for cognitive science","volume":"1","author":"Eliasmith C.","year":"2000","journal-title":"Cognitive Science Quarterly"},{"key":"e_1_2_11_27_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1017542632653"},{"key":"e_1_2_11_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36383-1_3"},{"key":"e_1_2_11_29_1","doi-asserted-by":"publisher","DOI":"10.1006\/jmps.1993.1036"},{"key":"e_1_2_11_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(95)00073-9"},{"key":"e_1_2_11_31_1","volume-title":"Parameterized complexity theory","author":"Flum J.","year":"2006"},{"key":"e_1_2_11_32_1","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/5684.001.0001"},{"key":"e_1_2_11_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00377-2"},{"key":"e_1_2_11_34_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1017503201702"},{"key":"e_1_2_11_35_1","first-page":"55","volume-title":"The universal Turing machine: A half\u2010century survey","author":"Gandy R.","year":"1988"},{"key":"e_1_2_11_36_1","volume-title":"Computers and intractability: A guide to the theory of NP\u2010completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_11_37_1","volume-title":"Efficient parallel algorithms","author":"Gibbons A.","year":"1988"},{"key":"e_1_2_11_38_1","doi-asserted-by":"publisher","DOI":"10.1037\/0033-295X.103.4.650"},{"key":"e_1_2_11_39_1","first-page":"10","article-title":"Gaps in Penrose's toilings","volume":"2","author":"Grush R.","year":"1995","journal-title":"Journal of Consciousness Studies"},{"key":"e_1_2_11_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0010-0277(02)00184-1"},{"key":"e_1_2_11_41_1","first-page":"1","volume-title":"Proceedings of the Dagstuhl Seminar on Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs","author":"Hamilton M.","year":"2007"},{"key":"e_1_2_11_42_1","volume-title":"Categorical perception: The groundwork of cognition","author":"Harnad S.","year":"1987"},{"key":"e_1_2_11_43_1","volume-title":"Cognitive science and folk psychology: The right frame of mind","author":"Haselager W. F. G.","year":"1997"},{"key":"e_1_2_11_44_1","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/2105.001.0001"},{"key":"e_1_2_11_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00974186"},{"key":"e_1_2_11_46_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015634729532"},{"key":"e_1_2_11_47_1","first-page":"203","volume-title":"Optimality in biological and artificial networks","author":"Jagota A.","year":"1997"},{"key":"e_1_2_11_48_1","volume-title":"An introduction to parallel algorithms","author":"Jaja J.","year":"1992"},{"key":"e_1_2_11_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/323233.323242"},{"key":"e_1_2_11_50_1","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/4932.001.0001","volume-title":"Neural network design and the complexity of learning","author":"Judd J. S.","year":"1990"},{"key":"e_1_2_11_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0255(00)00043-8"},{"key":"e_1_2_11_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_11_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01565439"},{"key":"e_1_2_11_54_1","first-page":"17","volume-title":"The universal Turing machine: A half\u2010century survey","author":"Kleene S. C.","year":"1988"},{"key":"e_1_2_11_55_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0140525X00079644"},{"key":"e_1_2_11_56_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0140525X00072472"},{"key":"e_1_2_11_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00297511"},{"key":"e_1_2_11_58_1","doi-asserted-by":"crossref","DOI":"10.1145\/300307.1040360","volume-title":"Elements of the theory of computation","author":"Lewis H. R.","year":"1998"},{"key":"e_1_2_11_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2606-0"},{"key":"e_1_2_11_60_1","doi-asserted-by":"publisher","DOI":"10.1207\/s15516709cog0000_59"},{"key":"e_1_2_11_61_1","volume-title":"Vision: A computational investigation into the human representation and processing visual information","author":"Marr D.","year":"1982"},{"key":"e_1_2_11_62_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015516217425"},{"key":"e_1_2_11_63_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008313020307"},{"key":"e_1_2_11_64_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.ps.44.020193.002123"},{"key":"e_1_2_11_65_1","doi-asserted-by":"publisher","DOI":"10.2307\/2678447"},{"key":"e_1_2_11_66_1","first-page":"2231","volume-title":"Proceedings of the 1999 Congress on Evolutionary Computation","author":"Narayanan A.","year":"1999"},{"key":"e_1_2_11_67_1","first-page":"237","volume-title":"Principles of knowledge representation","author":"Nebel B.","year":"1996"},{"key":"e_1_2_11_68_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-1-4832-1446-7.50040-6"},{"key":"e_1_2_11_69_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-1-4832-1446-7.50009-1"},{"key":"e_1_2_11_70_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"e_1_2_11_71_1","first-page":"31","volume-title":"Rationality: Psychological and philosophical perspectives","author":"Oaksford M.","year":"1993"},{"key":"e_1_2_11_72_1","doi-asserted-by":"publisher","DOI":"10.4324\/9780203345955"},{"key":"e_1_2_11_73_1","volume-title":"Combinatorial optimization: Algorithms and complexity","author":"Papadimitriou C. H.","year":"1988"},{"key":"e_1_2_11_74_1","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/1836.001.0001"},{"key":"e_1_2_11_75_1","first-page":"125","volume-title":"Optimality in biological and artificial networks","author":"Parberry I.","year":"1997"},{"key":"e_1_2_11_76_1","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780198519737.001.0001"},{"key":"e_1_2_11_77_1","volume-title":"Shadows of the mind","author":"Penrose R.","year":"1994"},{"key":"e_1_2_11_78_1","first-page":"93","volume-title":"The large, the small and the human mind","author":"Penrose R.","year":"1997"},{"key":"e_1_2_11_79_1","doi-asserted-by":"publisher","DOI":"10.7771\/1932-6246.1009"},{"key":"e_1_2_11_80_1","volume-title":"Mind as motion: Explorations in the dynamics of cognition","author":"Port R. F.","year":"1995"},{"key":"e_1_2_11_81_1","doi-asserted-by":"publisher","DOI":"10.2307\/2269031"},{"key":"e_1_2_11_82_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198506287.003.0004"},{"key":"e_1_2_11_83_1","doi-asserted-by":"publisher","DOI":"10.1207\/s15516709cog2603_6"},{"key":"e_1_2_11_84_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/41.6.357"},{"key":"e_1_2_11_85_1","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/2004.001.0001","volume-title":"Computation and cognition: Towards a foundation for cognitive science","author":"Pylyshyn Z.","year":"1984"},{"key":"e_1_2_11_86_1","first-page":"189","volume-title":"Architectures for intelligence","author":"Pylyshyn Z.","year":"1991"},{"key":"e_1_2_11_87_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(80)90014-4"},{"key":"e_1_2_11_88_1","first-page":"311","volume-title":"Proceedings of the 13th annual conference of the Cognitive Science Society","author":"Rensink R. A.","year":"1991"},{"key":"e_1_2_11_89_1","volume-title":"Computational structure of human language","author":"Ristad E. S.","year":"1990"},{"key":"e_1_2_11_90_1","volume-title":"The language complexity game","author":"Ristad E. S.","year":"1993"},{"key":"e_1_2_11_91_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-505850-6.50010-4"},{"key":"e_1_2_11_92_1","doi-asserted-by":"publisher","DOI":"10.1016\/0010-0285(75)90024-9"},{"key":"e_1_2_11_93_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)00092-1"},{"key":"e_1_2_11_94_1","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/5236.001.0001","volume-title":"Parallel distributed processing. Explorations in the microstructure of cognition. Volume 1: Foundations","author":"Rumelhart D. E.","year":"1986"},{"key":"e_1_2_11_95_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"e_1_2_11_96_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0140525X00079681"},{"key":"e_1_2_11_97_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90178-3"},{"key":"e_1_2_11_98_1","doi-asserted-by":"publisher","DOI":"10.2307\/2550441"},{"key":"e_1_2_11_99_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511598951.005"},{"key":"e_1_2_11_100_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.ps.41.020190.000245"},{"key":"e_1_2_11_101_1","volume-title":"The harmonic mind: From neural computation to optimality\u2010theoretic grammar","author":"Smolensky P.","year":"2006"},{"key":"e_1_2_11_102_1","unstructured":"Stege U. Van Rooij I.Computing maximum coherence: A hard nut to crack2006Paper presented at the 39th annual meeting of the Society for Mathematical Psychology. Vancouver British Columbia."},{"key":"e_1_2_11_103_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015603317236"},{"key":"e_1_2_11_104_1","doi-asserted-by":"publisher","DOI":"10.1080\/00455091.1993.10717325"},{"key":"e_1_2_11_105_1","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/1900.001.0001"},{"key":"e_1_2_11_106_1","doi-asserted-by":"publisher","DOI":"10.1207\/s15516709cog2201_1"},{"key":"e_1_2_11_107_1","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/2524.001.0001"},{"key":"e_1_2_11_108_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0140525X00003447"},{"key":"e_1_2_11_109_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0140525X00079577"},{"key":"e_1_2_11_110_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-21591-4_6"},{"key":"e_1_2_11_111_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s2-42.1.230"},{"key":"e_1_2_11_112_1","doi-asserted-by":"publisher","DOI":"10.1037\/0033-295X.84.4.327"},{"key":"e_1_2_11_113_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0403402101"},{"key":"e_1_2_11_114_1","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(86)90022-1"},{"key":"e_1_2_11_115_1","doi-asserted-by":"publisher","DOI":"10.1037\/0033-295X.103.3.429"},{"key":"e_1_2_11_116_1","first-page":"1","volume-title":"Handbook of theoretical computer science, Volume A: Algorithms and complexity","author":"Van Emde Boas P.","year":"1990"},{"key":"e_1_2_11_117_1","doi-asserted-by":"publisher","DOI":"10.2307\/2941061"},{"key":"e_1_2_11_118_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0140525X98001733"},{"key":"e_1_2_11_119_1","doi-asserted-by":"publisher","DOI":"10.1142\/9789812815354_0002"},{"key":"e_1_2_11_120_1","volume-title":"Tractable cognition: Complexity theory in cognitive psychology","author":"Van Rooij I.","year":"2003"},{"key":"e_1_2_11_121_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmp.2005.01.002"},{"key":"e_1_2_11_122_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm034"},{"key":"e_1_2_11_123_1","first-page":"2622","volume-title":"Proceedings of the 28th annual conference of the Cognitive Science Society","author":"Van Rooij I.","year":"2006"},{"key":"e_1_2_11_124_1","unstructured":"Wareham T.The role of parameterized computational complexity theory in cognitive modelingInLing C. X. Sun R.(Eds.) Working Notes of the AAAI\u201096 Workshop on Computational Cognitive Modeling: Source of the Power1996."},{"key":"e_1_2_11_125_1","volume-title":"Systematic parameterized complexity analysis in computational phonology","author":"Wareham T.","year":"1999"},{"key":"e_1_2_11_126_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44674-5_26"},{"key":"e_1_2_11_127_1","doi-asserted-by":"publisher","DOI":"10.1145\/253769.253801"},{"key":"e_1_2_11_128_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/47.1.4"},{"key":"e_1_2_11_129_1","doi-asserted-by":"publisher","DOI":"10.1207\/s15516709cog2203_1"},{"key":"e_1_2_11_130_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-005-9003-0"}],"container-title":["Cognitive Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1080%2F03640210801897856","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1080%2F03640210801897856","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1080\/03640210801897856","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,26]],"date-time":"2024-10-26T16:46:36Z","timestamp":1729961196000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1080\/03640210801897856"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,9]]},"references-count":129,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2008,9]]}},"alternative-id":["10.1080\/03640210801897856"],"URL":"https:\/\/doi.org\/10.1080\/03640210801897856","archive":["Portico"],"relation":{},"ISSN":["0364-0213","1551-6709"],"issn-type":[{"value":"0364-0213","type":"print"},{"value":"1551-6709","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,9]]},"assertion":[{"value":"2008-09-01","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}