按年被提到
20112013 · 2 次2026
物理与量子›计算的物理极限·arXiv:1108.1791 · cs.CC

Why Philosophers Should Care About Computational Complexity

为什么哲学家应该关心计算复杂性
Scott Aaronson · 2011

Aaronson 论证复杂性理论如何改变哲学议题

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 5 人首次 2011-08-11 · 最近 2026-04-15
5不同的人
7活跃月份
7讨论串
143被引(OpenAlex)

文章详细论证:一件事一旦知道可计算,其计算效率并非只有实践意义,计算复杂性理论(研究解决计算问题所需的时间、空间和随机性等资源)能给许多哲学议题带来新视角,包括数学知识的本质、强人工智能之争、计算主义、逻辑全知问题、休谟的归纳问题、古德曼的 grue 谜题、量子力学基础、经济理性和闭合类时曲线等。文末还讨论了复杂性理论自身有哪些方面可以从哲学分析中受益。

HN 为什么提它

HN 上的人把它当作说明复杂性理论为何比可计算性更有意思、对哲学有何意义的优秀入门文章,在不同年份的相关讨论中反复被推荐。

观点难度 3 / 5约 150 分钟经得起时间
读之前最好知道
1可计算性与图灵机
2计算复杂性基础(P 与 NP)
3基础哲学(认识论、归纳问题)
4量子计算概念

学习路径

读这篇之前,按顺序读书架上的 4 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出

先建立量子计算与 NP 完全问题的物理可解性背景,再读 Aaronson 如何把复杂性理论带入哲学议题。

  1. 1

    它说明量子计算能做和不能做什么,是理解量子计算在复杂性层面界限的基础。

    读量子计算对搜索问题的加速上限,以及为何不能指望它轻易解决 NP 完全问题。

  2. 2
    Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer量子计算机上素因数分解与离散对数的多项式时间算法 · 1995

    Shor 算法是量子计算超越经典计算的最重要例子,文章多处以它为参照。

    读整数分解与离散对数问题的量子多项式时间算法的大意,数学细节可略。

  3. 3
    Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems非线性量子力学意味着可在多项式时间内求解 NP 完全与 #P 问题 · 1998

    它是假想的非线性量子力学使 NP 完全问题易解的例子,说明物理定律与复杂性的联系。

    读非线性修正为何带来额外计算能力,只读结论与动机。

  4. 4
    NP-complete Problems and Physical RealityNP 完全问题与物理现实 · 2005

    同一作者的另一篇综述,讨论物理手段能否高效求解 NP 完全问题,直接支撑哲学论证中的物理视角。

    读各种物理方案为何不能在多项式时间内解 NP 完全问题,抓住其中的共同模式。

  5. 5
    Why Philosophers Should Care About Computational Complexity为什么哲学家应该关心计算复杂性 · 2011 · 就是这篇

    在前述复杂性与物理背景下,看复杂性理论如何影响认识论与人工智能等哲学议题。

    读逻辑全知问题、休谟归纳问题、强 AI 争论等章节,关注复杂性视角带来的新论证。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
推荐eru · 2013-01

“is a good read about this---amongst other things.”

推荐它,称对这个话题等多方面都值得一读
Moore’s Law won’t kill passwords原评论 ↗
推荐eru · 2025-06

“excellent 'Why Philosophers Should Care About Computational Complexity': Why Philosophers Should Care About Computational Complexity”

称它是讲复杂性理论为何对哲学重要的优秀读物
AGI is Mathematically Impossible 2: When Entropy Returns原评论 ↗
引用Locke1689 · 2013-02

“as outlined in Scott Aaranson's paper:”

引用 Scott Aaronson 这篇论文,说明简单性可预测模型的正确性
Is Scientific Truth Always Beautiful?原评论 ↗
引用eru · 2026-04

“Compare Why Philosophers Should Care About Computational Complexity and why computational complexity is often more interesting that computability.”

拿它说明为何计算复杂性往往比可计算性更有意思
Not all elementary functions can be expressed with exp-minus-log原评论 ↗
被提交为 story · 3 次