{
  "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
}