In Mark Sprevak & Matteo Colombo (eds.), The Routledge Handbook of the Computational Mind. Oxford, UK: pp. 339-353 (2018)
AbstractWe overview logical and computational explanations of the notion of tractability as applied in cognitive science. We start by introducing the basics of mathematical theories of complexity: computability theory, computational complexity theory, and descriptive complexity theory. Computational philosophy of mind often identifies mental algorithms with computable functions. However, with the development of programming practice it has become apparent that for some computable problems finding effective algorithms is hardly possible. Some problems need too much computational resource, e.g., time or memory, to be practically computable. Computational complexity theory is concerned with the amount of resources required for the execution of algorithms and, hence, the inherent difficulty of computational problems. An important goal of computational complexity theory is to categorize computational problems via complexity classes, and in particular, to identify efficiently solvable problems and draw a line between tractability and intractability. We survey how complexity can be used to study computational plausibility of cognitive theories. We especially emphasize methodological and mathematical assumptions behind applying complexity theory in cognitive science. We pay special attention to the examples of applying logical and computational complexity toolbox in different domains of cognitive science. We focus mostly on theoretical and experimental research in psycholinguistics and social cognition.
Added to PP
Historical graph of downloads
References found in this work
Reasoning About Knowledge.Ronald Fagin, Joseph Y. Halpern, Yoram Moses & Moshe Vardi - 1995 - MIT Press.
Citations of this work
Descriptive Complexity, Computational Tractability, and the Logical and Cognitive Foundations of Mathematics.Markus Pantsar - 2021 - Minds and Machines 31 (1):75-98.
Similar books and articles
Why Philosophers Should Care About Computational Complexity.Scott Aaronson - 2013 - Computability: Turing, Gödel, Church, and Beyond:261--328.
Numerical Methods, Complexity, and Epistemic Hierarchies.Nicolas Fillion & Sorin Bangu - 2015 - Philosophy of Science 82 (5):941-955.
Universality, Invariance, and the Foundations of Computational Complexity in the Light of the Quantum Computer.Michael Cuffaro - 2018 - In Sven Hansson (ed.), Technology and Mathematics: Philosophical and Historical Investigations. Springer. pp. 253-282.
Deterministic Chaos and Computational Complexity: The Case of Methodological Complexity Reductions. [REVIEW]Theodor Leiber - 1999 - Journal for General Philosophy of Science / Zeitschrift für Allgemeine Wissenschaftstheorie 30 (1):87-101.
Computational Complexity Analysis Can Help, but First We Need a Theory.Todd Wareham, Iris van Rooij & Moritz Müller - 2008 - Behavioral and Brain Sciences 31 (4):399-400.
Elementary Arithmetic.Geoffrey E. Ostrin & Stanley S. Wainer - 2005 - Annals of Pure and Applied Logic 133 (1):275-292.
Intractability and the Use of Heuristics in Psychological Explanations.Iris Rooij, Cory Wright & Todd Wareham - 2012 - Synthese 187 (2):471-487.
Computational Complexity of Polyadic Lifts of Generalized Quantifiers in Natural Language.Jakub Szymanik - 2010 - Linguistics and Philosophy 33 (3):215-250.
Complexity and Postmodernism: Understanding Complex Systems.Paul Cilliers - 1998 - Routledge.
Computational Complexity on Computable Metric Spaces.Klaus Weirauch - 2003 - Mathematical Logic Quarterly 49 (1):3-21.