计算理论

可计算性理论

Computability Theory

在第一台电子计算机被制造出来之前整整十年，数学家们已经严格地证明了：某些问题，无论计算机有多强大，永远无法被程序所解决。这不是工程的局限，而是数学的边界——一条永远不会因为技术进步而后退的线。 可计算性理论研究的正是这条边界：什么样的问题在原则上是可以被机械化地求解的，什么样的问题在原则上不行，以及这两者之间的区分意味…

可计算性 · 停机问题 · 邱奇-图灵论题

被 3 个领域引用（哲学思想、宇宙学、宇宙物理）

计算复杂性理论

Computational Complexity Theory

1971 年，斯蒂芬·库克（Stephen Cook）在 ACM 会议上提出了一个问题，此后五十年没有人能够解决，而且极有可能在人类文明的有生之年都无法解决：P 是否等于 NP？ 这不只是计算机科学的问题，它关系到密码学的根基、人工智能的边界，甚至哲学意义上"数学发现是否可以被机械化"的问题。克莱数学研究所在 2000…

P vs NP · NP完全 · 多项式规约

被 10 个领域引用（数学、哲学思想、经济学、宇宙物理、化学、宇宙学、地球科学、人类历史、生命科学、政治学）

信息论

Information Theory

一个最基本的问题，直到 1948 年才有了精确答案："信息"到底是什么，如何量化它？ 在克劳德·香农发表《通信的数学理论》之前，"信息量"是一个直觉概念——人们知道长电报比短电报包含"更多信息"，嘈杂线路会让通信"更不可靠"，但这些描述都是定性的。香农做的事，是把这些直觉转化为严格的数学——由此诞生的信息论，成为数字通…

信息熵 · 信道容量 · 编码

被 10 个领域引用（宇宙物理、生命科学、语言学、哲学思想、经济学、人类历史、宇宙学、医学与公共卫生、政治学、工程与技术）

自动机与形式语言

Automata and Formal Languages

任何一门编程语言——Python、C、Haskell——在被计算机"读懂"之前，都必须经过一个关键步骤：把源代码字符串解析为结构化的语法树。这个过程依赖的理论，是自动机与形式语言——一套把"什么是合法字符串"的问题变成精确数学的工具。 但这套理论的起点，是语言学而非编程，是一位研究人类语言结构的语言学家在 1956 年…

有限自动机 · 下推自动机 · 乔姆斯基谱系

被 2 个领域引用（生命科学、语言学）

密码学基础

Foundations of Cryptography

1976 年，斯坦福大学的两位研究者惠特菲尔德·迪菲（Whitfield Diffie）和马丁·赫尔曼（Martin Hellman）发表了一篇论文，标题听起来平淡无奇：《密码学的新方向》（New Directions in Cryptography）。他们在其中解决了一个看似矛盾的问题：两个从未见过面、也没有秘密沟通…

公钥密码学 · 单向函数 · RSA

被 6 个领域引用（数学、哲学思想、宇宙物理、经济学、政治学、法学）

λ演算与类型理论

Lambda Calculus and Type Theory

数学中的函数，在教科书里通常被写成 $f(x) = x^2 + 1$ 的形式——$f$ 有个名字，$x$ 是变量，结果是某个表达式。1936 年，阿隆佐·邱奇（Alonzo Church）提出了一种不需要函数名字的写法：把函数本身当作一个对象，写成 $\lambda x.\, x^2 + 1$。这个 $\lambda$…

lambda演算 · 类型系统 · Curry-Howard对应

被 2 个领域引用（哲学思想、数学）

形式文法与乔姆斯基谱系

Formal Grammars and the Chomsky Hierarchy

1956 年，一位年轻的语言学家在 IRE《信息论汇刊》上发表了一篇论文：《语言描述的三个模型》（"Three Models for the Description of Language"）。他的问题是语言学的：如何用数学方法描述人类语言的结构？然而，他的答案成为了计算机科学的核心理论之一。 这位语言学家是诺姆·乔姆…

乔姆斯基谱系 · 形式文法 · 上下文无关文法

被 4 个领域引用（哲学思想、语言学、心理学、人类历史）

量子计算理论

Quantum Computing Theory

1994 年，美国数学家彼得·肖尔（Peter Shor）发表了一个算法。这个算法可以在多项式时间内分解大整数——而人类目前已知最好的经典算法（普通计算机上运行的算法）需要次指数时间。 这个差距有多大？分解一个 2048 位的 RSA 密钥，最好的经典算法需要数百万年；肖尔算法在一台足够大的量子计算机上，理论上只需要数…

量子计算 · BQP · 肖尔算法

被 4 个领域引用（宇宙物理、数学、化学、工程与技术）

柯莫哥洛夫复杂度

Kolmogorov Complexity

考虑两个字符串：

柯莫哥洛夫复杂度 · 算法信息论 · 随机性

被 4 个领域引用（数学、哲学思想、经济学、生命科学）

纠错码理论

Error-Correcting Codes

1977 年，旅行者 1 号从地球出发驶向木星和土星。无线电信号穿越数亿公里的真空，抵达接收天线时已经微弱到几乎无法与宇宙背景噪声区分。然而，旅行者传回的木星大气图像是清晰的。1986 年，旅行者 2 号飞过天王星，仍然发回了清晰照片——此时信号飞越将近 30 亿公里。 这不是因为接收天线足够大，或者无线电功率足够强。…

纠错码 · 汉明码 · Reed-Solomon码

被 9 个领域引用（哲学思想、生命科学、数学、政治学、宇宙物理、化学、宇宙学、经济学、工程与技术）

随机算法

Randomized Algorithms

一个算法，通常被认为是确定性的：给定相同的输入，它每次都执行相同的步骤，给出相同的输出。而随机算法（Randomized Algorithm）在执行过程中会抛硬币——使用随机数来做决策，使得同一输入在不同运行中可能走不同的路径。 这听起来像是在引入不可靠性。实际上，在很多问题上，随机化是到达正确答案最快、甚至唯一已知实…

随机算法 · 蒙特卡洛 · 拉斯维加斯

被 2 个领域引用（数学、哲学思想）

逻辑与计算

Logic and Computation

1958 年，数学家哈斯凯尔·加里（Haskell Curry）注意到一件奇怪的事：某些组合子逻辑（combinatory logic）的类型，与命题逻辑中的公式在形式上一模一样。 1969 年，数学家威廉·霍华德（William Howard）将这个观察系统化为一个深刻的对应：类型与命题是同一件事，程序与证明是同一件…

Curry-Howard对应 · 程序验证 · 类型论

被 2 个领域引用（哲学思想、生命科学）

计算几何

Computational Geometry

你每次用手机地图导航，都在隐式地使用计算几何。地图应用需要计算：你的位置附近有哪些餐厅（最近邻问题）；沿地图的多边形区域裁剪（多边形裁剪）；两条路是否交叉（线段相交）；如何优化无人机的送货路径（运动规划）。 计算几何（Computational Geometry）研究的是几何问题的高效算法——不只是"能解决"，而是"用…

计算几何 · 凸包 · Voronoi图

被 1 个领域引用（数学）

分布式计算理论

Theory of Distributed Computing

一台计算机出错，你重启它就好了。 但当成千上万台计算机通过会延迟、会丢包的网络协同工作时，一个全新的难题出现了：它们怎么对"现在到底发生了什么"达成一致？某台机器是真的崩溃了，还是只是网络慢了一拍？没有任何一台机器能看到全局。

共识 · FLP不可能性 · 拜占庭容错

被 2 个领域引用（经济学、政治学）

算法博弈论

Algorithmic Game Theory

1951 年，约翰·纳什证明了一件让经济学界震动的事：任何有限博弈，都至少存在一个均衡——一组策略，没有任何参与者能靠单方面改变策略而获益。这是博弈论的基石。 这个故事在纳什之前还有一章。1928 年，冯·诺依曼证明了二人零和博弈的极小极大定理——双方最优混合策略的存在性；1944 年他与摩根斯坦合著的《博弈论与经济行…

纳什均衡 · PPAD · 价格无政府

被 4 个领域引用（哲学思想、经济学、生命科学、政治学）

近似算法理论

Approximation Algorithms

假设你证明了一个问题是 NP 难的——比如规划全国快递车队的最优路线。这意味着（如果 P $\neq$ NP）你永远找不到一个又快又总能给出最优解的算法。 那就放弃吗？现实不允许。快递公司明天就要发车。

近似比 · NP难 · PCP定理

被 2 个领域引用（经济学、数学）

统计学习理论与 PAC 学习

Statistical Learning Theory and PAC Learning

机器学习最基本的问题不是"怎么把训练数据拟合好"——那件事平凡到可以用一张查找表完成。真正的问题是：为什么在训练集上表现好的模型，在没见过的数据上也会表现好？ 这个问题看起来像哲学（休谟的归纳问题），但从 1984 年起它有了一个数学答案的框架。莱斯利·瓦利安特那一年提出可能近似正确（Probably Approxim…

PAC 学习 · VC 维 · 泛化界

被 3 个领域引用（心理学、经济学、哲学思想）

在线算法与竞争分析

Online Algorithms and Competitive Analysis

绝大多数算法课教的是这样一个世界：输入摆在你面前，你可以从容读完再决定怎么做。 现实系统很少有这种奢侈。缓存要在不知道下一次访问什么的情况下决定淘汰谁；调度器要在不知道后续任务的情况下派活；云平台要在不知道明天流量的情况下决定扩不扩容；广告系统要在用户点击的那一瞬间决定投给谁，而预算是有限的。

在线算法 · 竞争比 · 缓存置换

交互式证明与零知识

Interactive Proofs and Zero Knowledge

"证明"这个概念在 1980 年代被重新定义了两次，每一次都让它变得更强。 第一次是加入交互与随机：证明不再是一份可以静态检查的文书，而是验证者与证明者之间的一场提问游戏，验证者可以掷硬币，并且只要求"以极高概率不被骗"。第二次更反直觉：证明可以让你确信某件事为真，而不透露任何关于为什么为真的信息。

交互式证明 · 零知识 · PCP 定理

为什么 P vs NP 这么难证：三道障碍

Why P vs NP Resists Proof: The Three Barriers

大多数关于 P 与 NP 的介绍会告诉你问题是什么、悬赏多少、以及"大家都相信 P ≠ NP"。很少有介绍讲这件事：我们不只是没证出来，我们还知道为什么整类看起来最自然的证明方法注定证不出来。 这三道被称为障碍的结果，是复杂性理论最独特的贡献之一——一门学科系统地研究自己的证明方法为何失效，并把结论写成定理。 它们让 …

P vs NP · 相对化 · 自然证明

计算的物理极限

The Physical Limits of Computation

复杂性理论问"这个问题需要多少步"。本篇问一个更基础的问题：一步计算，最少要花多少能量？ 答案不是零，而且它不取决于工艺、材料或聪明的电路设计——它由热力学第二定律给出。 这条边界对硅片、神经元和任何未来基底同样有效，它把"信息"与"熵"焊在了一起，顺带解决了一个困扰物理学近一个世纪的悖论。

兰道尔原理 · 可逆计算 · 麦克斯韦妖

通信复杂度

Communication Complexity

这是一个把"计算需要多少步"换成"两个人需要说多少话"的模型，而这个换法出人意料地强大。 爱丽丝手里有 $x$，鲍勃手里有 $y$，两人都有无限的算力，但要合作算出 $f(x,y)$。唯一被计量的是他们之间传送的比特数。 姚期智在 1979 年提出这个模型时，目标是分布式计算；它后来的主要用途却在别处——它成了证明各种…

通信复杂度 · 集合不相交 · 下界方法

平均情况复杂性与密码学的五个世界

Average-Case Complexity and the Five Worlds

NP 完全性说的是最坏情况：某个问题存在难解的实例。但最坏情况的难度对现实几乎没有承诺。 旅行商问题是 NP 完全的，而工业求解器每天处理着数万城市的实例；反过来，密码学需要的恰恰相反——它需要随机取一个实例就几乎必然难解。 "难"这个字在这两处指的不是同一件事，而这个区别决定了密码学能不能存在。

平均情况复杂性 · 单向函数 · 五个世界