dorsal/arxiv
View SchemaNP-complete Problems and Physical Reality
| Authors | Scott Aaronson |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0502072 |
| URL | https://arxiv.org/abs/quant-ph/0502072 |
| Journal | ACM SIGACT News, March 2005 |
Abstract
Can 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 NP-complete problems efficiently, I argue that by studying them, we can learn something not only about computation but also about physics.
{
"annotation_id": "f8bf5771-c331-4f68-81a6-954f11bea2e2",
"date_created": "2026-03-02T18:02:13.633000Z",
"date_modified": "2026-03-02T18:02:13.633000Z",
"file_hash": "7d52a13dc3156a39329575c0e2af336c76e714ef888e10e253ca426f29c6b61d",
"private": false,
"record": {
"abstract": "Can NP-complete problems be solved efficiently in the physical universe? I\nsurvey proposals including soap bubbles, protein folding, quantum computing,\nquantum advice, quantum adiabatic algorithms, quantum-mechanical\nnonlinearities, hidden variables, relativistic time dilation, analog computing,\nMalament-Hogarth spacetimes, quantum gravity, closed timelike curves, and\n\"anthropic computing.\" The section on soap bubbles even includes some\n\"experimental\" results. While I do not believe that any of the proposals will\nlet us solve NP-complete problems efficiently, I argue that by studying them,\nwe can learn something not only about computation but also about physics.",
"arxiv_id": "quant-ph/0502072",
"authors": [
"Scott Aaronson"
],
"categories": [
"quant-ph",
"cs.CC",
"gr-qc"
],
"journal_ref": "ACM SIGACT News, March 2005",
"title": "NP-complete Problems and Physical Reality",
"url": "https://arxiv.org/abs/quant-ph/0502072"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "09754a71-dd3b-414e-9487-f3c1d3c0dace",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}