---
abstract: 'Can $\mathsf{NP}$-complete problems be solved efficiently in the physical universe?  I survey proposals including soap bubbles, protein folding, quantum computing, quantum advice, quantum adiabatic algorithms, quantum-mechanical nonlinearities, hidden variables, relativistic time dilation, analog computing, Malament-Hogarth spacetimes, quantum gravity, closed timelike curves, and “anthropic computing.”  The section on soap bubbles even includes some “experimental” results.  While I do not believe that any of the proposals will let us solve $\mathsf{NP}$-complete problems efficiently, I argue that by studying them, we can learn something not only about computation but also about physics.'
author:
- 'Scott Aaronson[^1]'
bibliography:
- 'thesis.bib'
title: 'NP-complete Problems and Physical Reality'
---

Introduction\[INTRO\]
=====================

> Let a computer smear—with the right kind of quantum randomness—and you create, in effect, a ‘parallel’ machine with an astronomical number of processors … All you have to do is be sure that when you collapse the system, you choose the version that happened to find the needle in the mathematical haystack.
>
> —From *Quarantine* [@egan], a 1992 science-fiction novel by Greg Egan

If I had to debate the science writer John Horgan’s claim that basic science is coming to an end [@horgan], my argument would lean heavily on one fact: 