Descriptive Complexity, Computational Tractability, and the Logical and Cognitive Foundations of Mathematics
Minds and Machines 31 (1):75-98 (2021)
AbstractIn computational complexity theory, decision problems are divided into complexity classes based on the amount of computational resources it takes for algorithms to solve them. In theoretical computer science, it is commonly accepted that only functions for solving problems in the complexity class P, solvable by a deterministic Turing machine in polynomial time, are considered to be tractable. In cognitive science and philosophy, this tractability result has been used to argue that only functions in P can feasibly work as computational models of human cognitive capacities. One interesting area of computational complexity theory is descriptive complexity, which connects the expressive strength of systems of logic with the computational complexity classes. In descriptive complexity theory, it is established that only first-order systems are connected to P, or one of its subclasses. Consequently, second-order systems of logic are considered to be computationally intractable, and may therefore seem to be unfit to model human cognitive capacities. This would be problematic when we think of the role of logic as the foundations of mathematics. In order to express many important mathematical concepts and systematically prove theorems involving them, we need to have a system of logic stronger than classical first-order logic. But if such a system is considered to be intractable, it means that the logical foundation of mathematics can be prohibitively complex for human cognition. In this paper I will argue, however, that this problem is the result of an unjustified direct use of computational complexity classes in cognitive modelling. Placing my account in the recent literature on the topic, I argue that the problem can be solved by considering computational complexity for humanly relevant problem solving algorithms and input sizes.
Similar books and articles
Tractability and the computational mind.Rineke Verbrugge & Jakub Szymanik - 2018 - In Mark Sprevak & Matteo Colombo (eds.), The Routledge Handbook of the Computational Mind. Oxford, UK: pp. 339-353.
Cognitive and Computational Complexity: Considerations from Mathematical Problem Solving.Markus Pantsar - 2021 - Erkenntnis 86 (4):961-997.
Computational Complexity Theory and the Philosophy of Mathematics†.Walter Dean - 2019 - Philosophia Mathematica 27 (3):381-439.
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.
Modeling complexity: cognitive constraints and computational model-building in integrative systems biology.Miles MacLeod & Nancy J. Nersessian - 2018 - History and Philosophy of the Life Sciences 40 (1):17.
A fresh look at research strategies in computational cognitive science: The case of enculturated mathematical problem solving.Regina E. Fabry & Markus Pantsar - 2019 - Synthese 198 (4):3221-3263.
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.
Why philosophers should care about computational complexity.Scott Aaronson - 2013 - Computability: Turing, Gödel, Church, and Beyond:261--328.
A Step towards a Complexity Theory for Analog Systems.K. Meer & M. Gori - 2002 - Mathematical Logic Quarterly 48 (S1):45-58.
Logics which capture complexity classes over the reals.Felipe Cucker & Klaus Meer - 1999 - Journal of Symbolic Logic 64 (1):363-390.
Computational complexity of some Ramsey quantifiers in finite models.Marcin Mostowski & Jakub Szymanik - 2007 - Bulletin of Symbolic Logic 13:281--282.
Exploring the tractability border in epistemic tasks.Cédric Dégremont, Lena Kurzen & Jakub Szymanik - 2014 - Synthese 191 (3):371-408.
Added to PP
Historical graph of downloads
Citations of this work
Bootstrapping of integer concepts: the stronger deviant-interpretation challenge.Markus Pantsar - 2021 - Synthese 199 (3-4):5791-5814.
Objectivity in Mathematics, Without Mathematical Objects†.Markus Pantsar - 2021 - Philosophia Mathematica 29 (3):318-352.
On the development of geometric cognition: Beyond nature vs. nurture.Markus Pantsar - 2022 - Philosophical Psychology 35 (4):595-616.
From Maximal Intersubjectivity to Objectivity: An Argument from the Development of Arithmetical Cognition.Markus Pantsar - forthcoming - Topoi:1-11.
References found in this work
Computation and Cognition: Toward a Foundation for Cognitive Science.Zenon W. Pylyshyn - 1984 - Cambridge: MIT Press.
The Foundations of Arithmetic.Gottlob Frege - 1884/1950 - Evanston: Ill., Northwestern University Press.
On Computable Numbers, with an Application to the Entscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.
Shadows of the Mind: A Search for the Missing Science of Consciousness.Roger Penrose - 1994 - Oxford University Press.
The Emperor's New Mind: Concerning Computers, Minds, and the Laws of Physics.Roger Penrose - 1999 - Oxford University Press.