Minds and Machines 31 (1):75-98 (2021)

Markus Pantsar
University of Helsinki
In 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.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1007/s11023-020-09545-4
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 70,192
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

The Foundations of Arithmetic.Gottlob Frege - 1884/1950 - Evanston: Ill., Northwestern University Press.
On Computable Numbers, with an Application to the N Tscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.

View all 49 references / Add more references

Citations of this work BETA

Add more citations

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.
Computational Model Theory: An Overview.M. Vardi - 1998 - Logic Journal of the IGPL 6 (4):601-624.
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.
Tractable Competence.Marcello Frixione - 2001 - Minds and Machines 11 (3):379-397.
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.


Added to PP index

Total views
15 ( #697,956 of 2,507,391 )

Recent downloads (6 months)
3 ( #209,626 of 2,507,391 )

How can I increase my downloads?


My notes