Computational Complexity Theory and the Philosophy of Mathematics†

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

Authors
Walter Dean
University of Warwick
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.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1093/philmat/nkz021
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 44,455
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

On Computable Numbers, with an Application to the Entscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.
Introduction to Metamathematics.Stephen Cole Kleene - 1954 - Journal of Symbolic Logic 19 (3):215-216.

View all 62 references / Add more references

Citations of this work BETA

No citations found.

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.
Effective Fractal Dimensions.Jack H. Lutz - 2005 - Mathematical Logic Quarterly 51 (1):62-72.
Computability, Complexity, Logic.E. Börger - 1989 - New York: U.S.A.Elsevier Science Pub. Co..
Incompleteness in the Finite Domain.Pavel Pudlák - 2017 - Bulletin of Symbolic Logic 23 (4):405-441.

Analytics

Added to PP index
2019-11-06

Total views
9 ( #787,988 of 2,272,225 )

Recent downloads (6 months)
9 ( #109,904 of 2,272,225 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature