Computational Complexity Theory and the Philosophy of Mathematics†

Philosophia Mathematica 27 (3):381-439 (2019)
  Copy   BIBTEX

Abstract

Computational complexity theory is a subfield of computer science originating in computability theory and the study of algorithms for solving practical mathematical problems. Amongst its aims is classifying problems by their degree of difficulty — i.e., how hard they are to solve computationally. This paper highlights the significance of complexity theory relative to questions traditionally asked by philosophers of mathematics while also attempting to isolate some new ones — e.g., about the notion of feasibility in mathematics, the $\mathbf{P} \neq \mathbf{NP}$ problem and why it has proven hard to resolve, and the role of non-classical modes of computation and proof.

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 100,793

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

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.

Analytics

Added to PP
2019-11-06

Downloads
90 (#227,660)

6 months
10 (#361,262)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

Logic in mathematics and computer science.Richard Zach - forthcoming - In Filippo Ferrari, Elke Brendel, Massimiliano Carrara, Ole Hjortland, Gil Sagi, Gila Sher & Florian Steinberger (eds.), Oxford Handbook of Philosophy of Logic. Oxford, UK: Oxford University Press.

Add more citations