ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR11-108 | 14th August 2011 05:42

Why Philosophers Should Care About Computational Complexity

RSS-Feed




Revision #2
Authors: Scott Aaronson
Accepted on: 14th August 2011 05:43
Downloads: 8871
Keywords: 


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, 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.



Changes to previous version:

Added brief remarks about pseudorandomness and homomorphic encryption; put the "lookup table argument" more clearly into the context of previous discussions about complexity and the Turing Test


Revision #1 to TR11-108 | 11th August 2011 10:13

Why Philosophers Should Care About Computational Complexity





Revision #1
Authors: Scott Aaronson
Accepted on: 11th August 2011 10:13
Downloads: 1893
Keywords: 


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.



Changes to previous version:

Incorporated suggestions by Joshua Zelinsky, Gil Kalai, Michael Collins, and Terrence Cole


Paper:

TR11-108 | 8th August 2011 21:51

Why Philosophers Should Care About Computational Complexity





TR11-108
Authors: Scott Aaronson
Publication: 8th August 2011 21:52
Downloads: 8012
Keywords: 


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.



ISSN 1433-8092 | Imprint