算法与理论计算机2015scottaaronson.com编辑精选
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
进阶 · 约 90 分钟读完前置知识：计算复杂性基础、P vs NP 问题、分析哲学常识
导读
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细节。作者主张复杂度界限可以充当认识论中的'有限理性'约束。
HN 关注点：HN 读者长期关注 P vs NP 与哲学的交叉，讨论焦点在于复杂度是否真的有形而上学地位、以及量子计算能否实现暴力搜索等具体技术质疑。
HN 评论精选
这几条评论里：支持 1 质疑 1 补充 2
质疑质疑复杂度的形而上学地位：P=NP 可能无实际意义，且物理中难以找到真正'在意'复杂度的现象
作为前量子物理学者，我不明白为什么计算机科学家把计算复杂度当作某种形而上学的东西，甚至认为宇宙会'在意'它。首先，即使 P=NP，实际差别可能很小（比如最简单的 NP 问题需要 O(n^1000)）；其次，很多问题连 O(n^2) 都承受不了（想想大数据），所以即使在 P 内，指数大小也很关键。一个有趣的物理例子是激发原子的自发辐射：看起来是指数衰减，但理论表明必须是多项式尾部（约 1/t^3 或 1/t^6），只是概率太低至今未观测到。所以，真的存在'在意'计算复杂度的物理效应吗？
stared查看英文原文
As an ex-physicist (quantum physics, now - data science), I am still puzzled why computer scientist consider computational complexity something metaphysical. Or even worse - a rule which universe should care about; look up considerations of non-local boxes and computational complexity (a generalization of quantum correlations; see Popescu-Rohrlich box). First, even the CS's nightmare (where P=NP) may mean little practical difference (e.g. the simplest 'NP' takes O(n^1000)). Second, for many problems even O(n^2) is too much (think of big data problems). (Also, given that computation requires physical resources, you cannot scale it arbitrarily.) So even in P the actual exponent matters a lot. One interesting, physical case is the spontaneous emission of a photon from an excited atom. It looks like an exponential decay, but the theory shows that the decay have to be polynomial (I don't remember it's power, if more like 1/t^3 or 1/t^6, but not too high). Up to my knowledge, we haven't detected the polynomial tail (because when it is, the probabilities are so low). So, is there a physical effect that cares about computational complexity? Or a phenomenon in which it matters that we can simulate it in "only" O(n^100), not O(2^n)?
补充梳理文章中停机问题与中文房间的复杂度论证，并追问量子计算与暴力搜索的关系
这篇文章很有用。容易的部分包括：有限内存系统的停机问题是可判定的——确定性程序要么停机要么重复之前的状态；真正的问题是能否比直接运行程序更快地判定结果，这是复杂度问题，很多 NP 难问题的平均情形远比最坏情形容易。'中文房间'同样受扩展性问题困扰——它是对问题极其低效的解法，关键在于能比穷举改进多少。之后文章变难了：我一直以为量子计算不能对因数分解这类问题做暴力搜索（利用多重宇宙？），是我错了吗？
Animats查看英文原文
That's a useful article. The easy parts include - The halting problem is decidable for systems with finite memory. That's simple enough; a deterministic program with finite memory must either halt or repeat a previous state. Now the question is, is there a faster way to determine the outcome than running the program? That's a complexity problem. One of those where the average case is much easier than the worse case. Many NP-hard problems are like that. - The same scaling issue applies to the "Chinese room", which is an extremely inefficient solution to the problem. The question is how much can you improve on exhaustive enumeration. Then it gets hard. I thought it was established that quantum computing is not going to allow brute-force search (using multiple universes?) on problems like factoring. Is that wrong?
支持认为 P vs NP 证明方法本身就有哲学意义
P≠NP 的证明方法无疑会揭示关于计算、进而关于逻辑、进而关于哲学的某种深刻的东西。复杂性理论至今如此困难，这本身就是有哲学意味的。
danharaj查看英文原文
The method of proof of P!=NP will undoubtedly tell us something deeply fundamental about computation and therefore logic and therefore philosophy. That complexity theory is so difficult thus far is in itself philosophically interesting.
补充补充同一作者的相关论文、博客和第三方介绍文章
可以对比同一作者的《The Ghost in the Quantum Turing Machine》，以及他非常精彩的博客。另外 SlateStarCodex 也有一篇关于 Scott Aaronson 的文章。
eru查看英文原文
Also compare the The Ghost in the Quantum Turing machine (http://www.scottaaronson.com/papers/giqtm3.pdf) by the same author, and his marvellous blog at http://www.scottaaronson.com/blog/ . There's also a slatestarcodex post about Scott Aaronson: http://slatestarcodex.com/2015/01/01/untitled/
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2015Hacker News 讨论帖160 分 · 43 评
- 2016Hacker News 讨论帖177 分 · 54 评
- 2018Hacker News 讨论帖173 分 · 22 评
- 2021Hacker News 讨论帖42 分 · 1 评
同领域还值得读
通信的数学理论
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 分钟编辑精选近线性时间内的最大流与最小费用流
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
给出了最大流与最小费用流的近线性时间精确算法，是理论计算机科学的重要突破。
算法与理论计算机2022 · 230 分 · 40 评 · 引用 8专业 · 约 120 分钟编辑精选