Descriptive Complexity, Computational Tractability, and the Logical and Cognitive Foundations of Mathematics

Minds and Machines 31 (1):75-98 (2020)
  Copy   BIBTEX


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.

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. Routledge. 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

133 (#131,321)

6 months
102 (#35,205)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Markus Pantsar
Aachen University of Technology