HackerPapers

arXiv:1108.1791cs.CC

Why Philosophers Should Care About Computational Complexity

Scott Aaronson

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.

arXiv comments
58 pages, to appear in "Computability: Gödel, Turing, Church, and beyond," MIT Press, 2012. Some minor clarifications and corrections; new references added
Journal reference
DOI
Subjects
cs.CCComputational Complexity quant-phQuantum Physics

On Hacker News

Linked by 3 identifiable commenters in 5 comments across 5 threads, from Jan 2013 to Jul 2026. Found in 3 HN submissions from Aug 2011 to Nov 2021. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments5 threads

  1. Synthesis is harder than analysis 1 comment

    • As someone who's always loved synthesizing ideas and having lightbulb moments, I find the headline flattering. I wonder, though, if there's any more rigorous and general analysis (hah!) of the complexity of these two modes of thought. EDIT: Fable 5 turned up some relevant…

      nopinsightView on HNParent context

  2. Not all elementary functions can be expressed with exp-minus-log 1 comment

    • You probably want a fast algorithm. Compare https://arxiv.org/abs/1108.1791 and why computational complexity is often more interesting that computability.

      eruView on HNParent context

  3. AGI is Mathematically Impossible 2: When Entropy Returns 1 comment

    • Indeed. And it's fairly trivial to see that computability isn't the right lens to view intelligence through: The classic Turing test takes place over a finite amount of time. Normally less than an hour, but we can arbitrarily give the interlocutor, say, up to a week. If you…

      eruView on HNParent context

  4. Is Scientific Truth Always Beautiful? 1 comment

    • This is 99% correct, but you're wrong about the last sentence. Actually, science is about the most accurate model, but it turns out that what we mean by "beauty," is actually about simplicity, and thus about correctness. There is a sound mathematical background behind simplicity…

      Locke1689View on HNParent context

  5. Moore’s Law won’t kill passwords 1 comment

    • Did you mean superset instead of subset? Anyway for my statement I was only interested deterministic polynomial time (perhaps with access to randomness) with or without quantum capabilities. "Why Philosophers Should Care About Computational Complexity"…

      eruView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.