https://arxiv.org/abs/1108.1791 close this message arXiv smileybones icon Global Survey In just 3 minutes, help us better understand how you perceive arXiv. Take the survey TAKE SURVEY Skip to main content Cornell University We gratefully acknowledge support from the Simons Foundation and member institutions. arXiv.org > cs > arXiv:1108.1791 [ ] Help | Advanced Search [All fields ] Search arXiv Cornell University Logo [ ] GO quick links * Login * Help Pages * About Computer Science > Computational Complexity arXiv:1108.1791 (cs) [Submitted on 8 Aug 2011 (v1), last revised 14 Aug 2011 (this version, v3)] Title:Why Philosophers Should Care About Computational Complexity Authors:Scott Aaronson Download PDF 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. 58 pages, to appear in "Computability: Godel, Turing, Comments: Church, and beyond," MIT Press, 2012. Some minor clarifications and corrections; new references added Subjects: Computational Complexity (cs.CC); Quantum Physics (quant-ph) Cite as: arXiv:1108.1791 [cs.CC] (or arXiv:1108.1791v3 [cs.CC] for this version) Submission history From: Scott Aaronson [view email] [v1] Mon, 8 Aug 2011 19:59:11 UTC (75 KB) [v2] Thu, 11 Aug 2011 08:22:12 UTC (77 KB) [v3] Sun, 14 Aug 2011 03:41:35 UTC (80 KB) Full-text links: Download: * PDF * PostScript * Other formats (license) Current browse context: cs.CC < prev | next > new | recent | 1108 Change to browse by: cs quant-ph References & Citations * INSPIRE HEP * NASA ADS * Google Scholar * Semantic Scholar 5 blog links (what is this?) DBLP - CS Bibliography listing | bibtex Scott Aaronson a export bibtex citation Loading... Bibtex formatted citation x [loading... ] Data provided by: Bookmark BibSonomy logo Mendeley logo Reddit logo ScienceWISE logo (*) Bibliographic Tools Bibliographic and Citation Tools [ ] Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) [ ] Litmaps Toggle Litmaps (What is Litmaps?) [ ] scite.ai Toggle scite Smart Citations (What are Smart Citations?) ( ) Code & Data Code and Data Associated with this Article [ ] arXiv Links to Code Toggle arXiv Links to Code & Data (What is Links to Code & Data?) ( ) Related Papers Recommenders and Search Tools [ ] Connected Papers Toggle Connected Papers (What is Connected Papers?) [ ] Core recommender toggle CORE Recommender (What is CORE?) ( ) About arXivLabs arXivLabs: experimental projects with community collaborators arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website. Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them. Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs and how to get involved. Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?) * About * Help * Click here to contact arXiv Contact * Click here to subscribe Subscribe * Copyright * Privacy Policy * Web Accessibility Assistance * arXiv Operational Status Get status notifications via email or slack