“is a good read about this---amongst other things.”
Why Philosophers Should Care About Computational Complexity
Aaronson 论证复杂性理论如何改变哲学议题
文章详细论证:一件事一旦知道可计算,其计算效率并非只有实践意义,计算复杂性理论(研究解决计算问题所需的时间、空间和随机性等资源)能给许多哲学议题带来新视角,包括数学知识的本质、强人工智能之争、计算主义、逻辑全知问题、休谟的归纳问题、古德曼的 grue 谜题、量子力学基础、经济理性和闭合类时曲线等。文末还讨论了复杂性理论自身有哪些方面可以从哲学分析中受益。
HN 上的人把它当作说明复杂性理论为何比可计算性更有意思、对哲学有何意义的优秀入门文章,在不同年份的相关讨论中反复被推荐。
学习路径
读这篇之前,按顺序读书架上的 4 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出先建立量子计算与 NP 完全问题的物理可解性背景,再读 Aaronson 如何把复杂性理论带入哲学议题。
- 1
它说明量子计算能做和不能做什么,是理解量子计算在复杂性层面界限的基础。
读量子计算对搜索问题的加速上限,以及为何不能指望它轻易解决 NP 完全问题。
- 2
Shor 算法是量子计算超越经典计算的最重要例子,文章多处以它为参照。
读整数分解与离散对数问题的量子多项式时间算法的大意,数学细节可略。
- 3
它是假想的非线性量子力学使 NP 完全问题易解的例子,说明物理定律与复杂性的联系。
读非线性修正为何带来额外计算能力,只读结论与动机。
- 4
同一作者的另一篇综述,讨论物理手段能否高效求解 NP 完全问题,直接支撑哲学论证中的物理视角。
读各种物理方案为何不能在多项式时间内解 NP 完全问题,抓住其中的共同模式。
- 5Why Philosophers Should Care About Computational Complexity
在前述复杂性与物理背景下,看复杂性理论如何影响认识论与人工智能等哲学议题。
读逻辑全知问题、休谟归纳问题、强 AI 争论等章节,关注复杂性视角带来的新论证。
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及“excellent 'Why Philosophers Should Care About Computational Complexity': Why Philosophers Should Care About Computational Complexity”
“as outlined in Scott Aaranson's paper:”
“Compare Why Philosophers Should Care About Computational Complexity and why computational complexity is often more interesting that computability.”
- Why Philosophers Should Care About Computational Complexity ↗franze · 2011-08-11 · 2 分
- Why Philosophers Should Care About Computational Complexity (2011) ↗headalgorithm · 2019-01-31 · 1 分
- Why philosophers should care about computational complexity (2011) ↗lordleft · 2021-11-16 · 171 分