The Library
Computational complexity theory and the philosophy of mathematics
Tools
Tools
Tools
Dean, Walter (2019) Computational complexity theory and the philosophy of mathematics. Philosophia Mathematica, 27 (3). pp. 381-439. doi:10.1093/philmat/nkz021 ISSN 0031-8019.
|
PDF
WRAP-computational-complexity-theory-philosophy-mathematics-Dean-2019.pdf - Accepted Version - Requires a PDF viewer. Download (1244Kb) | Preview |
Official URL: https://doi.org/10.1093/philmat/nkz021
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 P≠NP problem and why it has proven hard to resolve, and the role of non-classical modes of computation and proof.
| Item Type: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Divisions: | Faculty of Social Sciences > Philosophy | ||||||||
| Journal or Publication Title: | Philosophia Mathematica | ||||||||
| Publisher: | Oxford University Press | ||||||||
| ISSN: | 0031-8019 | ||||||||
| Official Date: | October 2019 | ||||||||
| Dates: |
|
||||||||
| Volume: | 27 | ||||||||
| Number: | 3 | ||||||||
| Page Range: | pp. 381-439 | ||||||||
| DOI: | 10.1093/philmat/nkz021 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Reuse Statement (publisher, data, author rights): | This is the peer reviewed version of the following article: Walter Dean, Computational Complexity Theory and the Philosophy of Mathematics, Philosophia Mathematica, Volume 27, Issue 3, October 2019, Pages 381–439, which has been published in final form at https://doi.org/10.1093/philmat/nkz021. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Use of Self-Archived Versions. | ||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||
| Date of first compliant deposit: | 4 October 2019 | ||||||||
| Date of first compliant Open Access: | 5 November 2021 | ||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
