Aaronson, Scott
(2011)
Why Philosophers Should Care About Computational Complexity.
[Preprint]
Abstract
One might think that, once we know something is computable, how efficiently it can be computed is a practical question with little further philosophical importance. In this essay, I offer a detailed case that one would be wrong. In particular, I argue that computational complexity theory---the field that studies the resources (such as time, space, and randomness) needed to solve computational problems---leads to new perspectives on the nature of mathematical knowledge, the strong AI debate, computationalism, the problem of logical omniscience, Hume's problem of induction and Goodman's grue riddle, the foundations of quantum mechanics, economic rationality, closed timelike curves, and several other topics of philosophical interest. I end by discussing aspects of complexity theory itself that could benefit from philosophical analysis.
| Item Type: |
Preprint
|
| Creators: |
|
| Additional Information: |
To appear in "Computability: Gödel, Turing, Church, and beyond," MIT Press, 2012 |
| Keywords: |
Turing Test, Chinese room, problem of induction, bleen/grue, computational learning theory, PAC-learning, computationalism, theoretical computer science, bounded rationality, omniscience, quantum computing |
| Subjects: |
Specific Sciences > Computation/Information > Classical
Specific Sciences > Biology > Evolutionary Theory
Specific Sciences > Computation/Information > Quantum
Specific Sciences > Artificial Intelligence
General Issues > Confirmation/Induction
Specific Sciences > Economics
General Issues > Formal Learning Theory
Specific Sciences > Mathematics
Specific Sciences > Physics > Quantum Mechanics |
| Depositing User: |
Dr. Scott Aaronson
|
| Date Deposited: |
10 Aug 2011 11:09 |
| Last Modified: |
10 Aug 2011 11:09 |
| Item ID: |
8748 |
| Subjects: |
Specific Sciences > Computation/Information > Classical
Specific Sciences > Biology > Evolutionary Theory
Specific Sciences > Computation/Information > Quantum
Specific Sciences > Artificial Intelligence
General Issues > Confirmation/Induction
Specific Sciences > Economics
General Issues > Formal Learning Theory
Specific Sciences > Mathematics
Specific Sciences > Physics > Quantum Mechanics |
| Date: |
9 August 2011 |
| URI: |
https://philsci-archive.pitt.edu/id/eprint/8748 |
Monthly Views for the past 3 years
Monthly Downloads for the past 3 years
Plum Analytics
Actions (login required)
 |
View Item |
![[img]](https://philsci-archive.pitt.edu/style/images/fileicons/application_pdf.png)
![[feed]](http://philsci-archive.pitt.edu/style/images/feed-icon-32x32.png){kind=icon}