“Related (amazing) paper by Scott Aaronson”
NP-complete Problems and Physical Reality
综述各种物理手段能否高效求解 NP 完全问题
Aaronson 综述了一系列试图在物理世界里高效求解 NP 完全问题的提议,包括肥皂泡、蛋白质折叠、量子计算、量子绝热算法、量子力学非线性、隐变量、相对论时间膨胀、模拟计算、Malament-Hogarth 时空、量子引力、闭合类时曲线和 anthropic computing,其中肥皂泡一节还带有「实验」结果。作者并不相信其中任何一个能做到,但认为研究它们能让我们对计算和物理都有所了解。
HN 上的人在讨论 P=NP、模拟计算与物理极限时反复提它,欣赏其把 NP 难作为物理约束来看的思路,称它有趣好读,是这一话题的经典文章。
学习路径
读这篇之前,按顺序读书架上的 3 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出先看量子计算机的能力与局限、以及量子力学非线性假设带来的后果,再读对各种物理手段能否求解 NP 完全问题的综述。
- 1
Shor 算法是量子计算威力的标志性结果,综述讨论量子计算能做什么时以此为基点。
读抓量子计算机为何能高效分解整数,以及它并没有解出 NP 完全问题。
- 2
说明量子计算机在搜索类问题上的局限,对应综述中量子计算无法高效解 NP 完全问题的论点。
读抓量子搜索的下界与对 NP 完全问题的含义。
- 3
若量子力学带有微小非线性,则可能高效解 NP 完全问题,是综述中单独讨论的一类提议。
读抓非线性假设如何带来计算能力提升;细节无需深究。
- 4NP-complete Problems and Physical Reality
综述各种物理手段能否高效求解 NP 完全问题。
读抓各类提议为何都没有成功,以及作者提出的把 NP 完全问题不可解视为物理原理的观点。
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及“This paper NP-complete Problems and Physical Reality explores what it means for physical reality. It's really interesting.”
“This is a good follow up read to the classic "NP-complete Problems and Physical Reality"[1]”
“I like Scott Aaronsons approach: Using NP hardness asumption as a physical constraint and seeing what follows.”
“Excellent paper and a fun read.”
“Only for sufficiently small definitions of "solve": NP-complete Problems and Physical Reality”
看全部 9 条 →
“Section 3 of Aaronson's paper[0] discusses this explicitly, and comes to the conclusion that”
“Reminds me of NP-complete Problems and Physical Reality”
“contains some thoughts about it: NP-complete Problems and Physical Reality”
- NP Complete Problems and Physical Reality ↗nyellin · 2011-12-27 · 1 分
- NP-complete Problems and Physical Reality (2005) ↗wfunction · 2015-01-25 · 94 分
- NP-Complete Problems and Physical Reality (2005) [pdf] ↗weinzierl · 2015-05-25 · 2 分
- NP-Complete Problems and Physical Reality (2005) ↗andyjohnson0 · 2015-07-14 · 88 分
- NP-Complete Problems and Physical Reality (2005) ↗maverick_iceman · 2016-11-29 · 5 分