PhilSci Archive

Why Philosophers Should Care About Computational Complexity

Aaronson, Scott (2011) Why Philosophers Should Care About Computational Complexity. [Preprint]

Download (455Kb) | Preview


    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.

    Export/Citation:EndNote | BibTeX | Dublin Core | ASCII/Text Citation (Chicago) | HTML Citation | OpenURL
    Social Networking:

    Item Type: Preprint
    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 > Computer Science > 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 07:09
    Last Modified: 10 Aug 2011 07:09
    Item ID: 8748

    Actions (login required)

    View Item

    Document Downloads