算法与计算机科学scottaaronson.com编辑精选
哲学家为什么应该关注计算复杂性（2011）
Why Philosophers Should Care About Computational Complexity (2011) [pdf]
2015 — 2018，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这是计算理论学者 Scott Aaronson 2011 年的长文，论证计算复杂性理论（P vs NP、可计算性、复杂度界限等）对哲学核心问题——如哥德尔定理、中文屋、知识论、因果与物理——有实质意义，而不只是技术细节。文章多次登上 HN 首页，被视为连接计算机科学与哲学的经典读物。
为什么经久不衰：它把复杂性理论从技术工具提升为哲学问题的分析框架，观点在十年后（尤其 AI 时代）依然新鲜且少有人系统阐述。
HN 评论精选
质疑复杂性理论是否具有真实的物理/形而上学意义
作为前量子物理学家、现数据科学家，我一直不解为什么计算机科学家把计算复杂性当作某种形而上学的东西，甚至当作宇宙应当遵循的规则。首先，即使 P=NP 这个噩梦成真，实际影响可能也不大（比如最简单的 NP 问题可能需要 O(n^1000)）。其次，对很多问题来说 O(n^2) 都太多了，所以即使属于 P，实际指数也很重要。有没有什么物理效应真的在乎计算复杂性？
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)?
指出文章中停机问题与中文屋部分的核心论证思路
这是一篇有用的文章。容易的部分包括：有限内存系统的停机问题是可判定的——确定性程序要么停机要么重复之前的状态；问题是有没有比直接运行程序更快的方法，这是复杂性问题。同样的规模问题也适用于'中文屋'——它是对问题极其低效的解法。之后文章就变难了。
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≠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.
对文中'瀑布论证'的有效性提出疑问
有人能解释一下文章第 6 节吗？整体很有趣，但我不确定'瀑布论证'是否成立：给定任何访问'瀑布预言机' W 的下棋算法 A，存在一个不访问 W、时间和空间需求相近的同样好的下棋算法 A'。为什么要假设存在 A'？即使存在，我们能否把 A 归约到 A'？
GlobalTraveler查看英文原文
Is there anyone on hacker news that could explain me secion 6 in this article? Overall the article is very interesting but I am not sure if the waterfall argument is valid. The waterfall conjecture was stated as : 'Given any chess-playing algorithm A that accesses a "waterfall oracle" W, there is an equally good--chess-playing algorithm A', with similar time and space requirements that does not access W.' From this we can assume that the article is a metaphor for us as external observer given semantics for computation. Thus by providing the reduction we showed that the computation in and of itself does not have semantics. However, why would we assume there to exists A'? Even if there is A', can't we reduce A -> A', and if we can reduces W to A, then by proxy W -> A'? Could somebody help me?
历次讨论
同类还值得读
位运算技巧集
Bit Twiddling Hacks
斯坦福页面上的经典位运算技巧合集，收录了 popcount、前导/尾随零、位反转、交换、舍入等大量技巧，并附有解释和性能讨论。
算法与计算机科学上首页 8 次 · 2011–2024graphics.stanford.edu编辑精选如何不按平均评分排序
How Not To Sort By Average Rating
经典文章解释了为什么按平均评分排序不可靠：只有少量评价的条目（比如仅一条五星）会轻易排到最前，而评价数量的差异被忽略。
算法与计算机科学上首页 7 次 · 2009–2024evanmiller.org编辑精选数据结构可视化
Data Structure Visualizations
旧金山大学 David Galles 教授制作的数据结构与算法交互式可视化网站，涵盖 B 树、红黑树、排序、图算法等，可逐步操作观察其运行过程。
算法与计算机科学上首页 6 次 · 2011–2021cs.usfca.edu编辑精选1996 年以来的计算机科学最佳论文奖
Best Paper Awards in Computer Science since 1996
Jeff Huang 维护的一个汇总页面，收录了自 1996 年以来计算机科学各主要会议的“最佳论文奖”获奖名单，并按年份和会议整理，方便读者一站式浏览历届获奖论文。
算法与计算机科学上首页 6 次 · 2010–2018jeffhuang.com编辑精选算法（Jeff Erickson）
Algorithms, by Jeff Erickson
伊利诺伊大学 Jeff Erickson 教授的算法课教材，免费在线开放。
算法与计算机科学上首页 5 次 · 2018–2022jeffe.cs.illinois.edu编辑精选