按年被提到
20052015 · 7 次2026
物理与量子›量子实验与纠缠·arXiv:quant-ph/0502072 · quant-ph

NP-complete Problems and Physical Reality

NP 完全问题与物理现实
Scott Aaronson · 2005

综述各种物理手段能否高效求解 NP 完全问题

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 13 人首次 2010-08-09 · 最近 2018-06-29
13不同的人
12活跃月份
14讨论串
164被引(OpenAlex)

Aaronson 综述了一系列试图在物理世界里高效求解 NP 完全问题的提议,包括肥皂泡、蛋白质折叠、量子计算、量子绝热算法、量子力学非线性、隐变量、相对论时间膨胀、模拟计算、Malament-Hogarth 时空、量子引力、闭合类时曲线和 anthropic computing,其中肥皂泡一节还带有「实验」结果。作者并不相信其中任何一个能做到,但认为研究它们能让我们对计算和物理都有所了解。

HN 为什么提它

HN 上的人在讨论 P=NP、模拟计算与物理极限时反复提它,欣赏其把 NP 难作为物理约束来看的思路,称它有趣好读,是这一话题的经典文章。

综述难度 4 / 5约 100 分钟经得起时间
读之前最好知道
1计算复杂度(P、NP 与 NP 完全)
2量子计算基础
3广义相对论与时空的基本概念
4模拟计算与物理系统的计算模型

学习路径

读这篇之前,按顺序读书架上的 3 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出

先看量子计算机的能力与局限、以及量子力学非线性假设带来的后果,再读对各种物理手段能否求解 NP 完全问题的综述。

  1. 1
    Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer量子计算机上素因数分解与离散对数的多项式时间算法 · 1995

    Shor 算法是量子计算威力的标志性结果,综述讨论量子计算能做什么时以此为基点。

    读抓量子计算机为何能高效分解整数,以及它并没有解出 NP 完全问题。

  2. 2

    说明量子计算机在搜索类问题上的局限,对应综述中量子计算无法高效解 NP 完全问题的论点。

    读抓量子搜索的下界与对 NP 完全问题的含义。

  3. 3
    Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems非线性量子力学意味着可在多项式时间内求解 NP 完全与 #P 问题 · 1998

    若量子力学带有微小非线性,则可能高效解 NP 完全问题,是综述中单独讨论的一类提议。

    读抓非线性假设如何带来计算能力提升;细节无需深究。

  4. 4
    NP-complete Problems and Physical RealityNP 完全问题与物理现实 · 2005 · 就是这篇

    综述各种物理手段能否高效求解 NP 完全问题。

    读抓各类提议为何都没有成功,以及作者提出的把 NP 完全问题不可解视为物理原理的观点。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
强烈推荐evanpw · 2015-12

“Related (amazing) paper by Scott Aaronson”

强烈推荐 Aaronson 这篇相关的精彩论文
A bad citizen in Javaland (2006)原评论 ↗
推荐alextp · 2010-08

“This paper NP-complete Problems and Physical Reality explores what it means for physical reality. It's really interesting.”

推荐它探讨对物理现实意味着什么,觉得很有意思
Ask HN: If P = NP, what does it mean?原评论 ↗
推荐weinzierl · 2015-05

“This is a good follow up read to the classic "NP-complete Problems and Physical Reality"[1]”

把这篇经典论文当作值得跟进的好读物
Is Quantum Mechanics an Island in Theoryspace? (2004) [pdf]原评论 ↗
推荐nabla9 · 2016-11

“I like Scott Aaronsons approach: Using NP hardness asumption as a physical constraint and seeing what follows.”

赞赏 Aaronson 的思路:把 NP 难假设当作物理约束,看会推出什么
The P=?NP Poll (2002) [pdf]原评论 ↗
推荐Rickasaurus · 2017-08

“Excellent paper and a fun read.”

称它是优秀的论文,读起来有趣
Ask HN: What is your favorite CS paper?原评论 ↗
引用jerf · 2012-05

“Only for sufficiently small definitions of "solve": NP-complete Problems and Physical Reality”

指出只有在对“求解”作很弱的定义时才成立,并附论文
Using A Slime-Mold To Calculate Minimum Spanning Trees原评论 ↗
看全部 9 条 →
引用ColinWright · 2015-08

“Section 3 of Aaronson's paper[0] discusses this explicitly, and comes to the conclusion that”

指出论文第 3 节明确讨论了此事,结论是物理模拟求解器对非平凡 NP 实例无效
An Argument for P=NP (2005) [pdf]原评论 ↗
引用chriswarbo · 2015-11

“Reminds me of NP-complete Problems and Physical Reality”

说它让自己想起这篇论文,涉及物理系统与 NP 完全问题的计算难度
Computability: The Greatest Law of Physics原评论 ↗
引用ScottAaronson · 2018-06

“contains some thoughts about it: NP-complete Problems and Physical Reality”

指出作者的综述对此有些想法,说明物理超计算机为何可能不存在
I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA原评论 ↗
被提交为 story · 5 次