算法与理论计算机2017arxiv.org
P 与 NP 问题的一个解？
A Solution of the P versus NP Problem?
专业 · 约 60 分钟读完前置知识：计算复杂性理论、P vs NP 问题背景、布尔电路复杂度
导读
这是 Norbert Blum 提交的一篇声称解决了 P vs NP 问题的论文，主张证明 P≠NP。该问题被视为理论计算机科学最重要的未解难题，此前已有上百次失败的尝试，因此社区普遍持谨慎态度，等待同行评审验证。
HN 关注点：P vs NP 是计算机科学最著名的千年难题，任何声称的证明都会引发巨大关注，而 HN 读者讨论的焦点是这份证明是否可信、以及如何快速判断这类声明是否值得认真对待。
后来怎么样
论文在提交数日内即被发现证明有误，作者随即主动撤稿，成为 P vs NP 无效证明的又一著名案例。
HN 评论精选
这几条评论里：支持 1 质疑 1 补充 3
质疑谨慎乐观：作者专业可信，但证明显得过于简单，且单作者署名令人存疑
这绝对是那种“我要等同行评审”的声明，但确实令人兴奋。优点：作者不是外行，而是在该领域活跃研究的学者。缺点：虽然不是我的领域，但我原本期待一个解决 P?NP 的方案会更有新意，这个看起来太简单了（几乎能写在页边空白处……）。可能是优点也可能是缺点：单一作者。重要的新工作没有多位作者正变得越来越罕见，尤其是来自职业学者的工作。不过，安德鲁·怀尔斯……
ajarmst查看英文原文
This is definitely one of those "I'm going to wait for the peer review" claims, but it is pretty exciting. Pros: The author is not a dilettante, and is actively researching in the area (http://theory.cs.uni-bonn.de/blum/Forschung/forsch.var) Cons: It's not my area, but I was expecting something a little more novel for a solution to P?NP. This almost seems too simple (it might almost fit in a margin...). Could be pro or con: Single author. It's becoming rare for important new work to not have multiple authors, especially from professional academics. However, Andrew Wiles...
补充补充资料：此前已有 116 个失败的“证明”，提醒大家保持怀疑
这里有一个列表，收录了此前 116 个对 P versus NP 问题的“解答”：http://www.win.tue.nl/~gwoegi/P-versus-NP.htm
DominikPeters查看英文原文
A list of 116 previous "solutions" to the P versus NP problem: http://www.win.tue.nl/~gwoegi/P-versus-NP.htm
补充引用 Scott Aaronson 的经典文章：如何快速鉴别这类证明是否值得读
Scott Aaronson 写过一篇文章：“假设有人给你一份对某个著名几十年数学难题（如 P vs NP）的复杂解答，你如何在十分钟内判断这份解答是否值得阅读？”
Tomte查看英文原文
Scott Aaronson on "suppose someone sends you a complicated solution to a famous decades-old math problem, like P vs. NP. How can you decide, in ten minutes or less, whether the solution is worth reading?": http://www.scottaaronson.com/blog/?p=304
补充后续进展：作者已通过 arXiv 的 v2 版本撤回该论文
给像我一样迟钝的人说明一下：作者上传了一个文件大小为 0 字节的 [v2]（见页面底部），这构成了对论文的撤回。[v2] 带有一条评论，大致在页面中部，就是本帖标题所引用的内容。你可以点击 [v1] 链接获取已被撤回内容的 PDF。我非常喜欢 arXiv 的版本化发布机制。
exikyut查看英文原文
For anyone dense like me: - The author has uploaded a [v2] with file size 0 bytes (see bottom of page); this constitutes retraction of the publication - [v2] has a comment, shown approximately partway down the page, which is what this post's subject cites You can click the [v1] link to get a PDF link to the now-retracted information. I really like arXiv's versioned publishing.
支持赞赏作者主动承认证明有误并撤稿的科学态度
一旦问题暴露就指出这种细节，这是多么了不起的人。轻松引导同行科学家走上正路！
sova查看英文原文
What a fantastic person to point out such a subtlety once it has come to light. Easily steer your fellow scientists right!
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2017Hacker News 讨论帖662 分 · 286 评
- 2017Hacker News 讨论帖258 分 · 78 评
同领域还值得读
哲学家为何应关注计算复杂性
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 分钟编辑精选