1971 年，斯蒂芬·库克（Stephen Cook）在 ACM 会议上提出了一个问题，此后五十年没有人能够解决，而且极有可能在人类文明的有生之年都无法解决：P 是否等于 NP？
这不只是计算机科学的问题，它关系到密码学的根基、人工智能的边界，甚至哲学意义上"数学发现是否可以被机械化"的问题。克莱数学研究所在 2000 年把它列为七个"千禧年问题"之一，悬赏 100 万美元——至今无人认领。
破除误解："难题"不等于"不可计算"
可计算性理论（见 computability）研究的是"能不能解"；复杂性理论研究的是"解起来有多费劲"。
图灵机原则上可以计算停机问题以外的一切可计算问题——但"原则上"往往意味着用宇宙年龄乘以宇宙中原子数量的计算步骤。一个问题可计算，不意味着它可以在实际中被高效解决。
复杂性理论的核心洞察是："高效"这个概念本身，可以被数学地定义和分类，而不同复杂度的问题之间，存在严格的层次结构。
现场：库克 1971 年的论文
斯蒂芬·库克 1971 年在 STOC（计算理论研讨会）发表了《定理证明程序的复杂性》，证明了布尔可满足性问题（SAT）是 NP 完全的。
SAT 问题：给定一个布尔逻辑公式（由变量、AND、OR、NOT 组成），是否存在一组变量赋值使公式为真？
库克证明了：任何 NP 问题都可以在多项式时间内规约到 SAT。也就是说，如果 SAT 有多项式算法，那么所有 NP 问题都有多项式算法——P = NP。
随后，理查德·卡普（Richard Karp）在 1972 年证明了另外 20 个经典问题都是 NP 完全的，包括旅行商问题、顶点覆盖、背包问题、哈密顿回路、图着色等（连同 SAT 共 21 个，史称"Karp 的 21 个 NP 完全问题"）。这一下子把 NP 完全性从一个孤立结果变成了横跨组合优化、图论、调度的庞大问题家族——它们"同生共死"：只要任何一个有了多项式算法，全部都有。NP 完全性理论由此成形。
（注：苏联数学家列昂尼德·列文（Leonid Levin）独立且几乎同时给出了等价的定义，在苏联文献中有时将 NP 完全称为"普遍问题"，卡普-库克-列文定理反映了这段并行历史。）
核心一：P 与 NP 的定义
P（多项式时间类）：所有存在多项式时间算法的判定问题的集合。如果问题的输入大小为 $n$，则算法运行时间为 （$k$ 为某常数）。
NP（非确定性多项式时间类）：所有"答案可以在多项式时间内被验证"的判定问题的集合。等价地，若存在一台非确定性图灵机能在多项式时间内解决它，则问题属于 NP。
注意：NP 不是"非多项式（non-polynomial）"，而是"非确定性多项式（nondeterministic polynomial）"——这是一个常见的误解。
P NP 是显然的（能解就能验证）。P 是否真的等于 NP（即"容易验证"是否意味着"容易求解"），是这个领域的核心未解问题。绝大多数计算机科学家相信 P NP，但截至 2026 年，这仍未被证明。
核心二：NP 完全与多项式规约
规约（Reduction）：问题 $A$ 多项式规约到问题 $B$（记作 ），意思是：存在一个多项式时间算法，把 $A$ 的任意实例转化为 $B$ 的一个实例，使得两个实例的答案相同。
如果 且 $B$ 有多项式算法，则 $A$ 也有。换句话说，$B$ "至少和 $A$ 一样难"。
NP 完全（NP-complete）：一个问题 $C$ 是 NP 完全的，当且仅当： 1. NP（答案可多项式验证） 2. 所有 NP 问题都可多项式规约到 $C$（即 $C$ 是 NP 中最难的）
如果 P NP（主流信念），则 NP 完全问题没有多项式时间算法——这意味着对大规模输入，只能诉诸近似算法（见 approximation-algorithms）、启发式方法或随机化算法（见 randomized-algorithms）。
核心三：复杂度类的层次
复杂性理论的版图远不止 P 和 NP：
| 类别 | 描述 |
|---|---|
| P | 多项式时间可解 |
| NP | 多项式时间可验证（答案为"是"时） |
| co-NP | NP 的补类（否定答案可多项式验证） |
| PSPACE | 多项式空间可解（时间不限） |
| EXPTIME | 指数时间可解 |
| BPP | 随机化多项式时间（允许有界错误概率） |
| BQP | 量子多项式时间（量子计算机的 P） |
已知的包含关系：。量子计算机所在的 BQP 与 NP 的确切关系尚未完全厘清。
代价与争议
P = NP 的后果：如果 P = NP，则现代公钥密码学的基础将崩塌——因为密码学依赖于某些问题（大整数分解、离散对数）"难以求解但易于验证"的性质（参见 cryptography-foundations）。许多机器学习、优化、药物设计中的 NP 难问题将变得可高效解决，影响将是根本性的。
近似与参数化复杂度：即使无法精确求解，能否找到近似解？对于有 $k$ 个解的特殊结构实例，能否有更快的算法？这催生了近似算法理论和参数化复杂度理论（FPT 类），是当前研究的活跃前沿。一个漂亮的"恰到好处"案例：Max-3-SAT 有简单的 7/8-近似算法（连随机赋值都能期望满足 7/8 的子句），而 Håstad（2001）借助 PCP 定理证明，任何多项式算法都无法做到比 7/8 更好（除非 P=NP）——上界与下界严丝合缝地咬在 7/8，这类"最优不可近似性"结果正是 PCP 定理最深刻的应用之一。
大量声称的证明：P vs NP 问题每年都会有数十篇声称"证明"（P = NP 或 P ≠ NP）的论文出现，几乎全部在同行评审中被推翻。Scott Aaronson 等研究者维护了这类错误证明的分析记录，成为复杂度理论社区的一种传统。
交互式证明系统与 PCP 定理
1980 年代，Goldwasser、Micali、Rackoff 引入了交互式证明系统（Interactive Proof Systems）的概念：证明者（Prover，计算能力无限）与验证者（Verifier，多项式时间有界的随机化机器）之间交互多轮，验证者以高概率判断证明者的断言是否成立。
引人注意的结果：IP = PSPACE（Shamir, 1990/1992，建立在 Lund-Fortnow-Karloff-Nisan 的代数方法之上）——交互式证明系统恰好能验证 PSPACE 中的所有问题，远强于 NP（只允许一轮非交互验证）。这个等式的反直觉之处在于：只要允许验证者掷硬币并和证明者多轮对话，能被高效验证的命题范围就一举从 NP 暴涨到整个 PSPACE。随机性与交互的组合，威力远超单独任一者——这也是零知识证明（见下文及 cryptography-foundations）能够存在的理论根基。
更深刻的是 PCP 定理（Probabilistically Checkable Proofs Theorem，1992 年由两篇 FOCS 论文共同确立：Arora-Safra 与 Arora-Lund-Motwani-Sudan-Szegedy，常合称 ALMSS）：任何 NP 问题的证明都可以被改写为一种"概率可检验证明"，使验证者只需随机读取证明的常数个符号，就能以高概率判断证明的正确性。用一个比喻：一份几百页的证明，验证者蒙上眼睛随机戳几个字，就能以极高概率分辨它是真证明还是骗局——这听上去不可思议，却是被严格证明的定理。
PCP 定理的重要推论是：很多 NP 完全问题的近似版本也是 NP 难的——不只是精确解难找，连好的近似解也难找。这统一了大量近似算法下界的证明，是 1990 年代复杂度理论最重要的成果之一。
随机化计算与 BPP
1970 年代，研究者注意到某些问题如果允许使用随机数，可以得到显著更快的算法。这催生了随机化复杂度的研究：
BPP（Bounded-error Probabilistic Polynomial time）：随机化多项式时间算法，允许有界错误率（答案错误概率 ）。重复多次并取多数票可以把错误概率降到任意低。
直觉上，随机化应该比确定性计算更强——毕竟多了一种资源。但令人惊讶的是，主流猜测是 P = BPP：任何有效随机算法都可以被去随机化，转化为确定性算法，而不损失太多效率。如果这是真的（至今未证明），随机性在计算中并没有本质的威力。
Adleman（1978）的定理已证明 BPP ⊆ P/poly（非均匀多项式时间），这是去随机化方向上的部分成果。
电路复杂度：另一条路
研究复杂度问题的一条路是电路复杂度（Circuit Complexity）：用布尔电路（AND/OR/NOT 门的有向无环图）来衡量计算复杂度，而不用图灵机时间步数。
电路复杂度在某些方面更精细：它区分了均匀计算（同一算法处理所有输入大小）和非均匀计算（不同大小的输入可以用不同电路）。
已知某些函数（如奇偶校验函数）不能被常数深度多项式规模的电路计算（Furst-Saxe-Sipser，1981；Razborov，1987），这是下界证明的少数成功案例之一。但证明对数深度电路无法计算 NP 完全问题，至今是未解问题——尽管人们普遍相信这是真的。
下界证明的困难，折射出 P vs NP 的深层障碍：我们有强大的工具证明算法的上界（找到快速算法），却极少有工具证明下界（证明不存在快速算法）。
跨域连接
- 纳什均衡：存在性由不动点定理给出，是非构造的；而一般博弈中计算均衡被归入一个被广泛相信不属于 P 的类。这把复杂度变成了对经济学的检验：若一个均衡连计算机都算不出来，"理性主体会落到那里"就不再是可信的行为预测，而只是一个存在性断言。
- 理性预期：该假设要求主体解出整个模型的解。计算复杂性由此给"有限理性"提供了一个不依赖心理学的理由——不是人算错了，而是那个解在原则上没有高效算法。检验也随之变硬：模型若把难解的求解嵌进主体头脑，它预测的就不是行为，而是一个无人能执行的理想。
- 密码学基础：密码学需要的比 P≠NP 更强。P vs NP 谈的是最坏情况，存在难实例即可；密码需要随机抽一个实例就难。这条最坏与平均之间的落差，正是"即便证明了 P≠NP 也未必得到单向函数"的原因，也是密码学至今建立在假设而非定理之上的原因。
- 线性规划：难与不难的分水岭常常正落在整数约束上：连续松弛可在多项式时间求解，加上取整要求就变 NP 难。近似算法的整套方法论靠的就是这条缝——先解松弛拿到一个可计算的下界，再把分数解舍入回整数，用两者的间隙量化损失。
- 证明：若 P=NP，"找到证明"与"检查证明"同样容易，数学发现将坍缩成搜索。这不该被当成乐观预期，而应读作一个反证的理由：多数人相信 P≠NP，部分正因为发现与验证之间那道经验上的鸿沟太宽，宽到很难相信它只是算法还没被想出来。
参考文献
- Cook, S. A. The Complexity of Theorem Proving Procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing (1971): 151–158. （NP 完全性原始论文）
- Karp, R. M. Reducibility Among Combinatorial Problems. In Complexity of Computer Computations. Plenum (1972). （20 个 NP 完全问题）
- Garey, M. R. & Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979). （经典参考书，含大量问题分类）
- Sipser, M. Introduction to the Theory of Computation. 3rd ed. Cengage Learning (2012). （第七章为复杂度理论入门）
- Shamir, A. IP = PSPACE. Journal of the ACM 39(4), 869–877 (1992). （初版 FOCS 1990）
- Arora, S. et al. Proof Verification and the Hardness of Approximation Problems. JACM 45(3), 501–555 (1998). （PCP 定理，初版 FOCS 1992）
- Håstad, J. Some Optimal Inapproximability Results. JACM 48(4), 798–859 (2001). （Max-3-SAT 的 7/8 紧界）
延伸阅读
- Aaronson, S. Quantum Computing Since Democritus. Cambridge University Press (2013). （深入浅出，涵盖 P vs NP 及量子复杂度）
纵轴是对数刻度下的运算次数——读数面板给出 n =16 时各类的真实数量级。注意 O(2ⁿ) 与 O(n!) 如何迅速冲破图顶：这正是为什么指数与阶乘级算法只能用于极小输入。 数值为示意性的渐近估计，忽略常数因子。