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

Pantsar Markus

摘要

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 (classical) 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.

机译：在计算复杂性理论中，决策问题被分为复杂性类，基于计算资源的算法来解决它们。在理论计算机科学中，通常认为只有用于解决复杂性P中的问题的功能，通过多项式时间在多项式时间中可以解决，被认为是易行的。在认知科学和哲学中，这种易无法解释的结果用于争论P中只能在人类认知能力的计算模型中可行的工作。一个有趣的计算复杂性理论是描述性复杂性，其与计算复杂性类别连接了逻辑系统的表现力强度。在描述性复杂性理论中，建立只有一阶（经典）系统连接到P，或其一个子类。因此，第二阶逻辑系统被认为是计算难治性的，因此似乎不适合模拟人类认知能力。当我们想到逻辑作为数学基础时，这将是有问题的。为了表达许多重要的数学概念和系统地证明涉及它们的定理，我们需要具有比古典一阶逻辑更强的逻辑系统。但如果这种系统被认为是棘手的，这意味着数学的逻辑基础对于人类认知来说可能是对人类认知的复杂性。在本文中，我将争辩说，这个问题是在认知建模中不合解的计算复杂性类别的不合理直接使用的结果。将我的帐户放在最近的文献中的主题，我认为通过考虑对人类相关问题解决算法和输入大小的计算复杂性可以解决问题。

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

摘要

著录项

相关主题

期刊订阅