PaperlayerView exact revision on arXiv

Source-linked AI summary

Why Philosophers Should Care About Computational Complexity

Scott Aaronson

arXiv:1108.1791v3cs.CCquant-ph

TL;DR

Computability alone leaves open whether problems can be solved efficiently, a distinction the essay argues matters beyond engineering. It surveys complexity theory’s perspectives on philosophical questions and concludes that they enrich debates across mathematics, mind, science, and rationality.

  • Problem

    Knowing that a problem is computable does not answer whether it can be solved efficiently, and the philosophical relevance of that question has received less attention than computability theory’s.

    Source: §1 · p. 2

  • Method

    The essay surveys complexity-theoretic ideas and applies them to philosophical problems including mathematical knowledge, induction, quantum mechanics, and economic rationality.

    Source: §12 · p. 48

  • Results

    The essay argues that computational complexity provides new insights into philosophical debates ranging from mathematical knowledge and computationalism to induction, quantum mechanics, and economic rationality.

    Source: §12 · p. 48

  • Takeaways & Limitations

    Complexity theory can enrich philosophical understanding without dissolving the problems it addresses.

    Source: §12 · p. 48

    Basic PAC learning assumes the learner is tested on the same distribution as the sample, limiting its fit to scientific prediction of phenomena different in kind from those observed.

    Source: §7.1 · p. 29

Abstract

from arXiv · show

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.

1 Introduction

Computational complexity shifts attention from whether problems are computable to whether they are efficiently or feasibly computable. The essay surveys how this perspective may clarify philosophical problems while acknowledging that it neither resolves them all nor covers every relevant connection.

1 Introduction

  • Complexity theory asks which computable problems can be solved efficiently, a question the essay argues has been underused in philosophy.The essay aims to help correct complexity theorists’ failure to communicate what the field can add to philosophy’s conceptual toolkit.Source: §1 · pp. 2–3
  • The essay offers perspectives on philosophical puzzles, not claims that complexity theory dissolves them.It also flags puzzles that complexity analysis leaves untouched or introduces.Source: §1 · p. 3

1.1 What This Essay Won’t Cover

  • The survey excludes or only briefly touches several connections, including programming-language semantics, distributed systems, and Kolmogorov complexity.It also mentions pseudorandom generators and fully homomorphic encryption as ideas it treats briefly or not at all.Source: §1.1 · p. 4

2 Complexity 101

Computational complexity studies how the resources needed to solve a problem scale with its size, often distinguishing polynomial from exponential time. The essay argues that this distinction has both practical and philosophical significance.

2 Complexity 101

  • Complexity theory asks how resource requirements scale with problem size, distinguishing growth such as n or n^2 from 2^n or n!.Multiplication has algorithms running in about n^2 or n log n log log n steps, while the fastest known factoring method cited uses about 2^n^(1/3) steps.Source: §2 · p. 5
  • Polynomial time is a convenient theoretical definition of efficiency, and it often corresponds empirically to practical efficiency, though intermediate growth rates and extreme constants complicate the identification.The essay notes that polynomial/exponential classification is largely independent of low-level encoding choices, while some modeling choices, such as quantum versus classical computation, can matter.Source: §2 · pp. 5–6
  • Complexity differs from computability by enabling questions connected to sciences such as evolution, quantum mechanics, and economics, while drawing on a wider range of mathematical techniques.The essay argues that complexity theory’s scientific connections make its philosophical relevance an important question.Source: §2 · p. 6

3 The Relevance of Polynomial Time

The essay uses polynomial-time complexity to connect computational feasibility with mathematical knowledge, evolution, and proof search. These examples make the polynomial/exponential gap a middle ground for philosophical distinctions that neither small quantitative differences nor computability alone captures.

3.1 The Entscheidungsproblem Revisited

  • If P = NP, finding proofs of reasonable length would be possible in reasonable time, making Hilbert’s dream of mechanizing mathematics prevail for practical purposes.The essay says the story of the Entscheidungsproblem is not over until P versus NP is solved.Source: §3.1 · pp. 7–8

3.2 Evolvability

  • Evolution can find some optimization solutions in polynomially many steps, unlike the exponentially long wait expected for a tornado to assemble a complex object by chance.The essay says evolvability research remains far from calculating from first principles whether geological time suffices for the human brain to evolve.Source: §3.2 · pp. 8–9

3.3 Known Integers

  • The contrast between a known prime and the first prime larger than it suggests that mathematical knowledge may depend on efficient access, not merely unique definition and proof.The essay notes that a known algorithm outputs the digits of 2^k − 1 in time polynomial, indeed linear, in the number of digits of the prime, but no similarly efficient algorithm is known for finding the next prime.Source: §3.3 · pp. 9–10

3.4 Summary

  • Polynomial-time complexity matters philosophically because it lies between model-sensitive small quantitative gaps and the overly broad finite-versus-infinite divide.The latter can overlook distinctions such as finding a solution versus verifying one, or classical versus quantum physics.Source: §3.4 · p. 10
  • The examples present the polynomial/exponential gap as a fertile area for philosophy beyond its role in theoretical computer science.The gap avoids both the technology-sensitive nature of small quantitative differences and the insensitivity of the finite/infinite distinction.Source: §3.4 · p. 10

4 Computational Complexity and the Turing Test

The section separates whether computers could count as minds from whether programs can practically pass the Turing Test. It argues that claims of practical impossibility require complexity bounds, while complexity does not settle metaphysical questions.

4 Computational Complexity and the Turing Test

  • The section frames the debate as two questions: whether a computer passing the Turing Test would count as minded, and whether such a program could be written.The essay says complexity theory offers perspectives on philosophical problems but does not dissolve them.Source: §4 · pp. 10–11

4.1 The Lookup-Table Argument

  • A finite upper bound on conversation length makes the lookup-table response computable, so computability alone cannot establish a fundamental obstacle to passing the Turing Test.The essay suggests a generous bound of 10^20 bits for realistic exchanges.Source: §4.1 · p. 12
  • The essay speculates that any program passing the Turing Test would require exponentially growing resources, but says the conjecture lacks compelling evidence and would be hard to prove.If true, the conjecture would imply that the brain could not be simulated within the observable universe’s resource constraints.Source: §4.1 · p. 13

4.2 Relation to Previous Work

  • Earlier complexity-based arguments about passing the Turing Test addressed Searle’s metaphysical question of sentience, whereas this essay uses complexity to address Penrose’s practical question of feasibility.The author declines to decide whether polynomial resource bounds themselves imply sentience.Source: §4.2 · p. 14

4.3 Can Humans Solve NP-Complete Problems Efficiently?

  • The author sees no reason to think humans solve NP-complete problems in polynomial time and doubts that humans efficiently solve even all problems in P.The author also questions what counts as unaided human computation, including whether pencil and paper are legitimate.Source: §4.3 · p. 14
  • Human strengths in art or poetry might be incomparable with mathematical problems, so neither task would necessarily reduce efficiently to the other.The essay notes that no polynomial-time algorithm for recognizing great art or poetry is known.Source: §4.3 · p. 15
  • Humans might outperform machines on structured NP-complete instances by spotting global patterns, while current proof-complexity results show exponential lower bounds for broad classes of algorithms on pigeonhole tautologies.The author says a proposed test based on higher-level patterns must explain those patterns and why machines could not detect them.Source: §4.3 · p. 15

4.4 Summary

  • Opponents of AI must choose between a metaphysical objection and conjecturing astronomical resource bounds; flat-out impossibility claims without quantitative complexity bounds are unavailable.The essay says such bounds are unlikely to be proved in the foreseeable future.Source: §4.4 · p. 16

5 The Problem of Logical Omniscience

Logical omniscience makes ordinary accounts of knowledge implausible, while complexity theory offers a limiting case: deductively closed knowledge of efficient algorithms need not imply computational omniscience.

5 The Problem of Logical Omniscience

  • Logical omniscience would make agents know every consequence of what they know, including facts such as Fermat’s Last Theorem, and would leave no room to contemplate already-known facts.The problem extends beyond mathematics and games to contemplation itself, a central activity and subject of philosophy.Source: §5 · p. 16

5.1 The Cobham Axioms

  • Bounded recursion and the smash function allow polynomial-length computations, while excluding exponentiation helps keep the axioms aligned with efficient computation.The smash function expands n-bit integers to n²-bit integers, enabling longer polynomial computations when combined with bounded recursion.Source: §5.1 · p. 19
  • The Cobham axioms characterize FP—the polynomial-time computable functions—as the smallest class satisfying five axioms.FP contains functions from natural numbers to natural numbers and is “morally” equivalent to P, which concerns decision problems.Source: §5.1 · pp. 19–20

5.2 Omniscience Versus Infinity

  • The proposed strategy is to understand knowledge as an ability to answer infinite families of questions efficiently, rather than as answers to isolated questions.For example, multiplication may be efficiently computable even when factoring is not, despite the related questions about 1591.Source: §5.2 · p. 20
  • The approach leaves open how agents learn algorithms and which infinite families questions should belong to, while asymptotic accounts can misclassify fixed problems with enormous constants.On an 8 × 8 chessboard, the cited estimate of about 10^60 steps is still a constant; the essay argues such cases rarely undermine asymptotic explanatory force.Source: §5.2 · pp. 21–22
  • An individual answer counts as knowledge only when an agent has a fast algorithm for a suitable generalization and recognizes the question as an instance of it.The same composite-number question may be hard in general but easy when the number ends in zero.Source: §5.2 · p. 21

5.3 Summary

  • Complexity theory does not yet solve logical omniscience generally, but the unbounded-question limit offers a case where closed axioms for knowing how avoid omniscience.The author presents this limiting case as a possible starting point for addressing the broader problem.Source: §5.3 · p. 22

6 Computationalism and Waterfalls

The waterfall argument treats computation as observer-relative and therefore semantically empty; complexity theory reframes the issue in terms of efficient reductions. Such reductions are non-vacuous only when their computational resources cannot already solve the problems at hand.

6 Computationalism and Waterfalls

  • A physical system can implement any desired mapping under suitable state labels, but this alone does not establish that its computation has semantic meaning.The waterfall argument uses this observer-relative view to challenge computationalism.Source: §6 · pp. 22–23
  • A meaningful test of whether a waterfall helps play chess requires an efficient encoding of chess positions and readout of moves; the author conjectures its oracle can be eliminated at similar cost.The conjecture would provide an observer-independent way to formalize the claim that waterfalls have no chess semantics.Source: §6 · p. 23

6.1 “Reductions” That Do All The Work

  • The analogy with NP-completeness exposes a flaw in defining P-completeness using polynomial-time reductions: the reducing algorithm can ignore its oracle and solve the problem itself.The proposed response is to require a weaker reducing class, such as LOGSPACE.Source: §6.1 · p. 24
  • Claims that a chess computation is equivalent to a waterfall simulation are non-vacuous only if the reductions use a model too weak to solve either problem on its own.This imports the complexity-theoretic lesson about reducing resources into debates about computationalism.Source: §6.1 · p. 24

7 PAC-Learning and the Problem of Induction

This section examines how PAC-learning connects reliable induction to hypothesis complexity and Occam’s Razor, while qualifying that account through limits on samples and computation, distribution shift, and language-dependent simplicity. It also considers how defining bleen and grue from green and blue affects complexity measures and relates this to bounded differences in description length across universal programming languages.

7 PAC-Learning and the Problem of Induction

  • For finite H, independent samples yield probability at least 1−δ that every consistent hypothesis has error at most ε, with required sample size growing logarithmically in |H|.The guarantee concerns future examples drawn from the same distribution as the training samples.Source: §7 · pp. 25–26
  • PAC-learning links Occam’s Razor to succinct descriptions: smaller hypothesis classes need fewer samples and reduce the risk of a hypothesis fitting the data by chance.The author presents the theorem as a mathematical rationale for preferring shorter or lower-complexity hypotheses, not other senses of simplicity.Source: §7 · p. 27

7.1 Drawbacks of the Basic PAC Model

  • VC-dimension extends the guarantee to infinite hypothesis classes: finite VC-dimension permits induction, whereas infinite VC-dimension can make PAC-learning impossible with any finite sample.The author treats finite VC-dimension as a necessary and sufficient condition for scientific induction within this framework.Source: §7.1 · pp. 27–28
  • PAC guarantees do not explain how to find a consistent hypothesis: many natural learning problems are computationally intractable, and under cryptographic assumptions some cannot be learned even with sufficient data.A polynomial-time learner in the cited setting would enable breaking widely used cryptosystems; learning pseudorandom functions would distinguish them from random functions.Source: §7.1 · pp. 28–29
  • Because PAC tests on the training distribution, it models prediction for similar observations rather than scientific explanations that reach novel or hypothetical phenomena.A mathematical model of explanatory learning with this kind of reach remains an open problem for the author.Source: §7.1 · p. 29

7.2 Computational Complexity, Bleen, and Grue

  • Complexity theory does not solve Goodman’s grue riddle: vocabulary can distort apparent simplicity, but for similarly expressive languages those differences matter less as learning problems grow.The author characterizes grue as a “small-n effect”; differences in expressive power can instead make some hypotheses exponentially longer to describe.Source: §7.2 · pp. 29–31
  • When the language can define green and blue in terms of bleen and grue, taking bleen and grue as primitive concepts raises κ_L(n) by only an additive constant, not a multiplicative one.The definitions can be made once and then referenced whenever needed.Source: §7.2 · p. 31
  • For any two Turing-universal programming languages, shortest-program lengths for any string differ by at most a universal translation constant, the bits needed to write an interpreter.The bound applies to every binary string x.Source: §7.2 · p. 31

8 Quantum Computing

The essay argues that quantum computing matters philosophically because it could probe the exponentiality of quantum mechanics and make interpretive questions harder to ignore. It uses quantum algorithms to examine the Many-Worlds interpretation while leaving the debate unresolved.

8 Quantum Computing

  • Building a quantum computer large enough for interesting problems remains an enormous engineering challenge because quantum states are fragile and must be isolated from their environment.The proposal is to exploit superposition and interference to solve certain computational problems faster than current methods.Source: §8 · p. 32
  • Shor’s polynomial-time factoring algorithm contrasts with best-known classical exponential-time algorithms, suggesting efficient-computation limits may depend on physical facts about quantum mechanics.The passage says Shor’s algorithm also provided key evidence that quantum computers would enlarge the class of problems solvable in polynomial time.Source: §8 · p. 32
  • A scalable quantum computer would test quantum mechanics in a regime defined by computational complexity, since n entangled particles require an exponentially large state vector.For a thousand spin-1/2 particles, the state vector has 2^1000 complex amplitudes.Source: §8 · p. 32
  • Quantum computing could directly probe quantum mechanics’ exponentiality, as Bell-inequality experiments made conceptually important aspects of the theory impossible to ignore.The author says quantum computing may likewise change the philosophical landscape.Source: §8 · p. 33

8.1 Quantum Computing and the Many-Worlds Interpretation

  • Superpolynomial quantum-over-classical speedup remains a conjecture, so polynomial-time hidden-variable theories remain open if that conjecture fails.The passage also notes that a fast classical factoring algorithm has not been ruled out.Source: §8.1 · p. 35
  • Exponential separations in the black-box model do not guarantee the same separation in conventional computation, since that model can mislead about the standard setting.The passage gives the equality IP = PSPACE despite a black box that separates them.Source: §8.1 · p. 35
  • Quantum algorithms do not simply try every answer in parallel: measurement reveals one outcome, so interference must cancel wrong paths and reinforce right ones.The passage says this delicate mechanism is known for only a few problems, mostly with special algebraic or number-theoretic structure.Source: §8.1 · p. 36
  • The parallel-worlds picture is in tension with interference: worlds useful for computation lose distinct identities, while distinct worlds are decohered and causally disconnected.The author argues that either feature complicates treating the computation as occurring across separate parallel universes.Source: §8.1 · p. 36

9 New Computational Notions of Proof

The essay contrasts familiar human and formal notions of proof with computational protocols, then explores how those protocols complicate ideas about mathematical knowledge. Zero-knowledge proofs and other complexity-theoretic proof forms raise questions about what establishes a theorem and what a prover must assume.

9 New Computational Notions of Proof

  • Complexity theory adds a third notion of proof: a computational process or protocol that terminates in a designated way if and only if the statement is true.The essay contrasts it with a human-facing explanation and a finite sequence of formal deductions from axioms.Source: §9 · pp. 36–37

9.1 Zero-Knowledge Proofs

  • In the graph non-isomorphism protocol, Merlin can answer every challenge for non-isomorphic graphs, while isomorphic graphs force some incorrect answers because random permutations are indistinguishable.Arthur challenges Merlin with a graph randomly permuted from either G or H.Source: §9.1 · p. 37
  • Repeated challenges make the protocol probabilistically more convincing, and interactive proofs can be shorter than the shortest known conventional proofs by an exponential factor.For an isomorphic pair, Merlin has a 1/2 chance of guessing correctly on each challenge; the passage says repetition reduces the chance of an unsound proof.Source: §9.1 · pp. 37–38
  • The graph protocol’s soundness assumes Merlin cannot spy on Arthur’s choice, making its persuasiveness partly dependent on an extramathematical belief about the prover’s powers.The passage says other complexity-theoretic proofs also rely on assumed limitations of provers.Source: §9.1 · p. 38
  • The graph non-isomorphism protocol is zero-knowledge: Arthur learns only the theorem’s truth, not why it holds or how to prove it to someone else.The protocol’s stated guarantee is that Arthur learns nothing beyond the truth of the statement being proved.Source: §9.1 · p. 38
  • The GMW protocol gives every statement with a conventional proof a zero-knowledge proof of comparable size, and its variants are used in Internet cryptography.The protocol relies essentially on a cryptographic hypothesis, and unlike graph non-isomorphism it needs only a polynomial-time prover who knows the proof.Source: §9.1 · p. 39

9.2 Other New Notions

  • Other proof notions include probabilistically checkable proofs, quantum proofs, multi-prover protocols, and computationally sound arguments, each with distinct assumptions or verification constraints.The PCP theorem says any theorem in a standard formal system can be converted in polynomial time to a probabilistically checkable format.Source: §9.2 · pp. 39–40
  • These proof forms raise open questions about whether physical assumptions in mathematical proof are merely familiar computational demands or something qualitatively new.The essay specifically asks whether reliance on quantum mechanics, randomness, or prover limitations changes the foundations of mathematics.Source: §9.2 · p. 40

10 Complexity, Space, and Time

Complexity theory distinguishes computational resources such as space and time, while closed timelike curves raise the prospect of turning those resources into unexpected computational power. The section argues that this power creates a computational paradox beyond the traditional grandfather paradox.

10 Complexity, Space, and Time

  • The author argues that complexity theory offers insight into the difference between space and time, although standard complexity classes are insensitive to some physical-space details.The stated equivalences include one-dimensional and multidimensional tapes and random-access machines, while spatial layout and communication can matter for polynomial-time differences and parallel computing.Source: §10 · p. 40
  • Generalized Hex is PSPACE-complete, while generalized chess is EXP-complete without a move bound and PSPACE-complete with a polynomial move bound.These classifications concern games generalized to an n × n board.Source: §10 · p. 41
  • Complexity theory treats space as more powerful than time because memory cells can be reused, whereas moments of time cannot.If backward time travel made time reusable, arbitrary PSPACE computations might become possible.Source: §10 · p. 42

10.1 Closed Timelike Curves

  • Deutsch's fixed-point proposal ensures consistent evolution for CTC experiments under quantum-mechanical or classically probabilistic laws, but its fixed points may be nonunique.A bit that loops unchanged through a CTC can have any value or probabilistic mixture as a fixed point; the passage says no boundary condition resolves this ambiguity.Source: §10.1 · pp. 42–43
  • Deutsch's proposal also faces a conflict with the statistical interpretation of quantum mixed states when a CTC interacts with one half of an entangled pair.Bennett et al.'s proposed remedy requires the CTC fixed point to be independent of the rest of the universe; the author calls this remedy so drastic that it effectively defines CTCs out of existence.Source: §10.1 · p. 43

10.2 The Evolutionary Principle

  • The central computational paradox is that a consistent CTC history could produce hard-to-create information, such as Shakespeare's plays, without anyone doing the work of writing them.The essay frames this as a violation of the commonsense Evolutionary Principle that knowledge requires a causal process to bring it into existence.Source: §10.2 · pp. 43–44

10.3 Closed Timelike Curve Computation

  • With polynomially bounded resources inside a CTC, causal consistency lets a computer solve NP-complete problems using only polynomial resources.For a problem with a valid solution, the described program's fixed points are exactly valid solutions; if none exist, its fixed points are uniform superpositions or probability distributions over all candidates.Source: §10.3 · pp. 44–45
  • Deutsch-model CTC computers solve all PSPACE problems, and PSPACE is also the limit for both classical and quantum CTC computers.The result supports the intuition that CTCs make space and time equivalent as computational resources; switching to quantum computation adds no benefit in this model.Source: §10.3 · pp. 44–45

11 Economics

The essay argues that computational limits complicate idealized economic rationality and reports that finding general-game equilibria is computationally hard. It also distinguishes such results from questions about how often that hardness matters in practice.

11 Economics

  • Even rational agents with perfect information may often find it computationally intractable to act in accordance with classical economics.The essay presents this as a contribution of complexity theory to debates about economic foundations, alongside the established bounded-rationality literature.Source: §11 · p. 46

11.1 Bounded Rationality and the Iterated Prisoners’ Dilemma

  • In the finite iterated Prisoner's Dilemma, backward induction predicts defection in every round, despite that outcome being against the players' interests and unlike human experimental behavior.Neyman's result restores cooperation as an equilibrium when both players have sufficiently small finite memories—k states for 2 ≤ k < N—because they cannot count up to the known number of rounds.Source: §11.1 · pp. 46–47
  • Aumann's agreement theorem persists even when Bayesian agents with common priors have limited communication.The essay presents this as an example of a counterintuitive conclusion that complexity considerations do not overturn.Source: §11.1 · p. 47

11.2 The Complexity of Equilibria

  • Finding a Nash equilibrium in a general two-player game is PPAD-complete, while zero-sum games can be solved in polynomial time.PPAD-completeness also applies to other fundamental economic problems, including finding market-clearing prices in Arrow-Debreu markets.Source: §11.2 · p. 47
  • The practical frequency of computational hardness in economic equilibrium problems remains an open question in the essay's discussion.The author argues that if Nash-equilibrium existence is relevant to debates such as free markets versus government intervention, then the PPAD-completeness of finding equilibria should be relevant too.Source: §11.2 · p. 47

12 Conclusions

The conclusion presents computational complexity as a source of philosophical insight while identifying limits and open questions about its real-world interpretation. It calls for philosophical analysis of the theory's assumptions, evidence, and relation to practice.

12 Conclusions

  • The essay argues that complexity theory offers insights across philosophical topics, including mathematical knowledge, computationalism, logical omniscience, quantum mechanics, closed timelike curves, and economic rationality.It suggests complexity is especially helpful for assessing whether a fact does explanatory work, rather than merely determining another fact.Source: §12 · p. 48
  • The author treats bedrock mathematical reality as a candidate philosophical problem that may lack important complexity-theoretic aspects.For example, the author regards a Turing machine's output as mathematically definite regardless of its resource requirements.Source: §12 · p. 48

12.1 Criticisms of Complexity Theory

  • Complexity theory's familiar limits include asymptotic claims that need not imply anything about finite problem sizes, unproved conjectures, restricted computational models, and a worst-case focus.The essay notes that worst-case hardness does not rule out effective heuristics for most instances arising in practice.Source: §12.1 · pp. 48–49
  • The author argues that complexity theory's imperfections do not justify dismissing its arguments; it can clarify which empirical predictions or mathematical conjectures a position commits to.The essay also notes that average-case complexity research has grown, while suitable probability distributions over inputs remain difficult to define.Source: §12.1 · pp. 49–50

12.2 Future Directions

  • The conclusion calls for philosophical analysis of the empirical status of asymptotic claims, intuitions about conjectures, and whether philosophical conclusions depend on conjectures such as P ≠ NP.It also raises how mathematicians make progress despite general theorem-proving intractability, including whether they select problems with special structure.Source: §12.2 · p. 50
Loading 1108.1791v3…