ECCC-Report TR11-108https://eccc.weizmann.ac.il/report/2011/108Comments and Revisions published for TR11-108en-usSun, 14 Aug 2011 05:43:01 +0300
Revision 2
| Why Philosophers Should Care About Computational Complexity |
Scott Aaronson
https://eccc.weizmann.ac.il/report/2011/108#revision2One 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.Sun, 14 Aug 2011 05:43:01 +0300https://eccc.weizmann.ac.il/report/2011/108#revision2
Revision 1
| Why Philosophers Should Care About Computational Complexity |
Scott Aaronson
https://eccc.weizmann.ac.il/report/2011/108#revision1One 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.Thu, 11 Aug 2011 10:13:28 +0300https://eccc.weizmann.ac.il/report/2011/108#revision1
Paper TR11-108
| Why Philosophers Should Care About Computational Complexity |
Scott Aaronson
https://eccc.weizmann.ac.il/report/2011/108One 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.Mon, 08 Aug 2011 21:52:01 +0300https://eccc.weizmann.ac.il/report/2011/108