算法与理论计算机2015arxiv.org编辑精选
NP 完全问题与物理实在（2005）
NP-complete Problems and Physical Reality (2005)
进阶 · 约 90 分钟读完前置知识：计算复杂性基础、NP 完全性、量子计算基础
导读
Scott Aaronson 2005 年的综述文章，考察「物理实在能否高效求解 NP 完全问题」：逐一检视量子计算、隐变量理论、拟人计算（anthropic computing）、封闭类时曲线等设想是否能让物理系统绕过 NP 困难性。核心结论是量子计算机并不能瞬时穷举求解 NP 完全问题，并据此讨论把「NP 完全问题对物理宇宙不可行」当作一条物理定律的可能性。
HN 关注点：Aaronson 把计算复杂性当作物理原理的大胆提法，以及文中关于隐变量、拟人计算等思辨性观点的可争议性。
后来怎么样
这篇综述成为“物理计算模型与复杂性”交叉领域的经典参考，明确了量子计算不能绕过 NP 困难性这一共识，并让“NP 不可行性作为物理定律”成为后续讨论中反复出现的命题。
HN 评论精选
这几条评论里：支持 1 补充 3
支持认为该论证足以否证隐变量理论的物理意义。
文中有一处隐藏亮点：「关键点在于，看到隐变量的历史，实际上会让我们能够模拟非坍缩的测量。」这一事实使我们可以把所有隐变量理论（当然包括玻姆的）斥为没有形而上学意义。隐变量是物理学里的隐形粉色独角兽。测不到的东西就不存在。接受现实吧。
lisper查看英文原文
Here's a hidden gem: "The key point is that seeing a hidden variable’s history would effectively let us simulate non- collapsing measurements." This fact allows one to dismiss all hidden-variables theories (including Bohm's of course) as having no metaphysical relevance. Hidden variables are the invisible pink unicorn of physics. If you can't measure it, it doesn't exist. Deal with it.
补充介绍作者背景、相关名篇与博客资源，并强调「NP 不可行性作为物理定律」的提法。
这是典型的 Scott Aaronson——他多次建议把「NP 困难问题对物理宇宙不可行」当作一条热力学定律，理由是支持它的证据至少和其他定律一样强，而一旦被推翻同样将是革命性的。他还有其他名篇：《谁能说出更大的数？》、用外行话解释 Shor 算法的《Shor，我来做》，以及《量子力学是理论空间中的一座孤岛？》，还有由博客变成课程再变成书的《Quantum Computing Since Democritus》。他的博客评论区常有大量争论（因为他观点鲜明），而他处理得十分搞笑，值得关注 Shtetl-Optimized。MIT 给他终身教职是明智的。
xnull2guest查看英文原文
This is classic Scott Aaronson - in fact, he's suggested on more than one occasion that we should adopt 'NP-hard problems are infeasible for the physical universe to solve' as a law of thermodynamics, arguing that the evidence for this is at least as good as other laws and that a disproof of this would be just as revolutionary. Other Aaronson classics include "Who can name the bigger number?" [1], "Shor, I'll do it" (his layman's explanation of Shor's algorithm for finding hidden abelian subgroups) [2], "Is Quantum Mechanics An Island In Theoryspace?" [3], and his blog turned class turned book "Quantum Computing Since Democritus" [4]. But really there's a ton of gold. He has a really neat explanation of the AKS primality testing algorithm [5] and modeled an imaginary easier-to-build (?) less-powerful-but-probably-more-powerful-than-classic-computers computing machine based on the quantum effects of light [6]. In general his blog tends to accumulate a lot of drama and controversy in its comments (because Prof. Aaronson is very opinionated), which he handles very hilariously. It's worth following him over at Shtetl-Optimized [7]. MIT was smart to have given him tenure. [1] http://www.scottaaronson.com/writings/bignumbers.html [2] http://www.scottaaronson.com/blog/?p=208 [3] http://www.scottaaronson.com/papers/island.pdf [4] http://www.scottaaronson.com/democritus/ [5] http://www.scottaaronson.com/writings/prime.pdf [6] http://www.scottaaronson.com/papers/optics.pdf [7] http://www.scottaaronson.com/blog/
补充指出拟人计算只是概率猜测，并追问实在的计算本性。
关于拟人计算：要注意，通过自杀并不会真正改善你的处境；在此之前和之后，你找到正确解的概率都还是 2^-n。拟人计算不过是「花哨的猜」。我觉得有趣的是：「实在的真实计算本性」必须允许你有足够的计算量，在指数多次（「并行」）中以对数时间验证你的解，否则你根本不可能在一个你知道自己已找到正确计算的世界里存在。这也让量子物理似乎不给我们任何「触及」这些幕后计算的方式显得奇怪。（除非实在的真实本性让波函数的一部分被「廉价」计算——坍缩洗清嫌疑？）
FeepingCreature查看英文原文
On the point of anthropic computing: it is important to note that you have not accomplished any _improvement_ to your condition by killing yourself; before as after, you had found a correct solution with probability 2^-n. Anthropic computing is just "fancy guessing". What is interesting about it to me is that the "true computational nature of reality" must be such that sufficient computation is available for you to run the _validation_ of your solution in logarithmic time an exponential number of times ("in parallel"), because otherwise you could not find yourself _at all_ in a universe where you knew you had found the correct computation. Which does make it strange that quantum physics does not seem to give us any way to "get at" all this computation that must be going on behind the scenes. (Unless the "true nature" of reality is such that a subset of the wavefunction is being computed "for cheap". Collapse exonerated?)
补充实践上 NP 完全问题有软硬之分，商用求解器和物理方法只对容易实例有效。
这些年越来越明显的一点是：NP 完全问题存在「松软」实例——可以在合理时间内找到好的近似；也存在同类问题中的「坚硬」实例——找不到好的近似。商业 ILP 求解器（如 Gurobi、CPlex）正是靠这一点获利：很多时候可以把 NP 完全问题建模并在可接受时间内求得良好解。同样，许多「物理」求解 NP 完全问题的方法对简单实例有效，一旦遇到困难实例就迅速变得不可驾驭。
sqrt17查看英文原文
A point that has become more obvious over the years is this: there are "soft" instances of NP-complete problems where you can find good approximations in reasonable time, and there are "crunchy" instances of the same class of problem where you don't find a good approximation. Commercial ILP solvers (e.g. Gurobi, CPlex) profit from the fact that quite often it is possible to formulate NP-complete problems and find good solutions in acceptable time. Similarly, many of the "physical" ways of solving NP-complete problems work ok for easy instances and get unwieldly fast if confronted with difficult instances.
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2015Hacker News 讨论帖94 分 · 16 评
- 2015Hacker News 讨论帖88 分 · 33 评
同领域还值得读
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细…
算法与理论计算机2015 · 552 分 · 120 评进阶 · 约 90 分钟编辑精选通信的数学理论
A Mathematical Theory of Communication
是香农1948年的《通信的数学理论》，为通信建立数学框架：把信息量定义为不确定性或自由度（信息熵），并讨论信源编码、信道容量与可靠传输。
算法与理论计算机2020 · 495 分 · 91 评进阶 · 约 120 分钟编辑精选物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态…
算法与理论计算机2009 · 390 分 · 55 评 · 引用 13专业 · 约 180 分钟编辑精选一种快速、极小内存的一致性哈希算法
A Fast, Minimal Memory, Consistent Hash Algorithm
论文给出一种快速、省内存的一致哈希方案，目标是在桶数量变化时保持较小的键迁移成本，同时降低计算和内存开销。
算法与理论计算机2014 · 327 分 · 57 评 · 引用 4进阶 · 约 25 分钟编辑精选第五个 Busy Beaver 值的确定
Determination of the fifth Busy Beaver value
宣布确定了第五个 Busy Beaver 值 BB(5)：即 5 状态图灵机中停机前运行步数最多的机器（Champion）在 47,176,870 步后停机。
算法与理论计算机2025 · 288 分 · 116 评 · 引用 1专业 · 约 75 分钟编辑精选