算法与理论计算机2017arxiv.org
求解困难优化问题出现指数级加速的证据？
Evidence of exponential speed-up in the solution of hard optimization problems?
进阶 · 约 45 分钟读完前置知识：计算复杂性基础（NP 完全）、组合优化、近似算法
导读
这篇论文针对困难优化问题提出一种非组合式求解方法，并报告实证结果：求解器随问题规模线性扩展，且能得到优于当前最先进方法的近似解，从而暗示可能存在指数级加速。评论普遍质疑该结论，因为方法给出的是近似解，且没有证明测试实例属于已知困难实例。
HN 关注点：是否真的绕过了 NP 完全问题的困难性，以及这类“指数加速”宣称是否只是近似解和容易实例上的结果。
HN 评论精选
这几条评论里：质疑 2 补充 2
质疑质疑论文只是近似解，且未证明测试的是已知困难实例。
摘要里说，这是一种针对困难优化问题的非组合方法，能找到比当前最先进方法更好的近似解。所以看起来他们找到的是近似解，重要性已经远低于标题暗示。接着又说求解器随问题规模线性扩展。我们知道多数 NP 完全问题的多数实例本来就容易；关键在于他们是否在已知困难的实例上测试。有可能他们只是像分解随机整数那样——几乎每个实例都容易。我非常悲观。
ColinWright查看英文原文
Quoting from the abstract: > ... a non-combinatorial approach > to hard optimization problems that > ... finds better approximations than > the current state-of-the-art. So it appears that they're finding approximate solutions, so already it's rather less significant than the title suggests. Then: > We show empirical evidence that > our solver scales linearly with > the size of the problem, ... We know that for most NP-Complete problems, most instances are easy. The question then is whether they are testing their algorithms on instances that are known to be hard. There's a chance they're doing something like finding factors of random integers, which we know is easy in almost every instance. I'm deeply pessimistic.
质疑认为此类宣称反复出现且缺乏具体成果，并引用 Aaronson 的批评。
这类东西每隔几个月就冒出来一次，已经好几年了，看起来像是胡扯。例如这个 HN 帖：https://news.ycombinator.com/item?id=8652475；还有 Scott Aaronson 的驳斥：https://www.scottaaronson.com/blog/?p=2212。如果这些人真能解 NP 完全问题，到现在应该能拿出一些惊人的具体结果，但他们没有。
colordrops查看英文原文
This keeps popping up every few months for several years, and seems like BS. Here's an example: https://news.ycombinator.com/item?id=8652475 And here's Scott Aaronson's debunking: https://www.scottaaronson.com/blog/?p=2212 If these guys could really solve NP complete problems, they should have some amazing concrete results to show at this point, which they don't.
补充补充作者创办的 SAT 求解器服务和相关批评文献。
作者基于这些想法创办了一家初创公司：http://memcpu.com/。他们把 SAT 求解器作为服务提供，可以试用。就此我推荐 Scott Aaronson 的相关论文《NP-complete Problems and Physical Reality》：https://www.scottaaronson.com/papers/npcomplete.pdf。
zmonx查看英文原文
The authors have built a start-up based on these ideas: http://memcpu.com/ They provide their SAT solver as a service that you can try. A related paper I recommend in this context is NP-complete Problems and Physical Reality by Scott Aaronson: https://www.scottaaronson.com/papers/npcomplete.pdf
补充提出与物理/模拟计算求解优化问题的类比疑问。
这是否类似 Berkeley MPC Lab 用电力做二次规划？也就是说，大自然有办法瞬间求解优化问题，而我们用微分方程近似这个过程，从而能做类似的事，虽然不是 100% 准确？
bitL查看英文原文
Is this similar to what Berkeley MPC Lab is doing with quadratic programming using electricity? I.e. that nature has means to solve optimization problems in an instant and our approximations of this process in the form of differential equations allow us to do something similar, albeit not 100% accurately?
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
- 评论区提到的论文
历次讨论
- 2017Hacker News 讨论帖141 分 · 38 评
同领域还值得读
哲学家为何应关注计算复杂性
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 分钟编辑精选