NP 完全性说的是最坏情况：某个问题存在难解的实例。但最坏情况的难度对现实几乎没有承诺。 旅行商问题是 NP 完全的，而工业求解器每天处理着数万城市的实例；反过来，密码学需要的恰恰相反——它需要随机取一个实例就几乎必然难解。
"难"这个字在这两处指的不是同一件事，而这个区别决定了密码学能不能存在。
破除误解
第一个误解：以为 P ≠ NP 就足以支撑密码学。 完全不够。P ≠ NP 只保证存在难实例，而密码学需要的是随机生成的实例几乎总是难的，并且需要求解者不知道答案而生成者知道。这三个要求逐级更强，而我们不知道前者是否蕴含后者。
第二个误解：以为"平均情况"就是随机取一个输入。 平均情况复杂性研究的是（问题，输入分布）这一对——同一个问题在不同分布下难度可以天差地别。没有指定分布的"平均情况难度"是一句没有内容的话。
第三个误解：以为这是密码学家的内部话题。 它是当前理论计算机科学最活跃的方向之一（元复杂性），并且直接决定了机器学习理论中"什么可以被高效学到"的边界——因为"难学"与"可用于加密"在形式上是同一件事的两面。
一、列文的问题：如何比较"平均难度"
1986 年，列昂尼德·列文为平均情况复杂性建立了形式框架，其中最微妙的是归约的定义。
最坏情况下，归约只需把实例映射过去。平均情况下，还必须保证分布也被合理地映射——否则可以把简单分布上的实例映射到困难分布的稀有区域，制造出虚假的困难。列文为此引入了"支配"条件：归约不能把源分布中高频出现的实例映射到目标分布中概率低得不成比例的实例上，二者的落差至多允许一个多项式因子。这条看似技术性的约束，正是整个理论区别于最坏情况理论的地方：难的载体从单个实例变成了实例与分布的组合，归约必须同时尊重两者。
归约之外，"容易"的定义同样需要重做。直觉上的"期望运行时间是多项式"并不合用：一批概率极低但慢得离谱的实例可以把期望撑爆，尽管实践中几乎永远碰不到它们。列文的定义转而要求运行时间随实例的稀有程度受控衰减——越慢的实例必须在分布中越稀有，且衰减速度压得住时间增长。这个定义配合支配条件，使得"分布式问题的易解性"在归约下封闭，整套理论才站得住。
在这个框架下，列文给出了第一个"分布式 NP 完全"问题——均匀分布上的有界铺砌问题：随机给定一组砖型和一条已铺好的边，判断能否铺满矩形。古列维奇后来把同一论证移植到有界停机问题上。值得注意的是列文本人的位置：他是 NP 完全性的独立发现者之一，平均情况理论可以看作他把同一纲领向"分布"维度推进的延续。
这套理论在提出后沉寂了相当长的时间。它被重新捡起，是因为人们发现密码学基础问题绕不开它——而这一次，推动者换成了元复杂性。
二、单向函数：密码学真正需要的东西
密码学的最小假设不是 P ≠ NP，而是单向函数存在：一个函数 $f$ 易于计算，但对随机取的 $x$，任何多项式时间算法从 $f(x)$ 恢复出原像的成功概率都可以忽略。注意这个定义里藏着两层平均情况：输入是随机取的，且失败概率要对几乎所有输入成立——这正是 P ≠ NP 无法提供的东西。
它的地位可以用一组等价关系说明——单向函数存在，当且仅当存在伪随机数生成器；当且仅当存在伪随机函数；当且仅当存在安全的私钥加密与数字签名。 这批等价性是 1980—90 年代的核心成果，它把散落的密码学原语归结到了同一个假设上。其中的技术高峰值得点名：Goldreich 与 Levin 1989 年证明从任何单向函数都能提取出一个"硬核谓词"——一个对求逆者不可预测的比特；Håstad、Impagliazzo、Levin 与 Luby 在此基础上完成了从任意单向函数到伪随机生成器的构造，整个证明跨越十年，是这个领域公认最艰难的定理之一。
注意这个假设比 P ≠ NP 强：单向函数存在蕴含 P ≠ NP，反之未知。因此"如果 P ≠ NP，那么密码学是安全的"这句流传很广的话是错的。
三、因帕利亚佐的五个世界
1995 年，因帕利亚佐提出了一个至今仍是这个领域组织框架的设想：根据这些假设的真假，我们可能生活在五个世界之一。
| 世界 | 成立的条件 | 后果 |
|---|---|---|
| Algorithmica | P = NP（或实际等价） | 优化、学习、定理证明全部变易；密码学不存在 |
| Heuristica | P ≠ NP，但 NP 问题平均情况容易 | 最坏情况的困难无法被利用；仍无密码学 |
| Pessiland | 平均情况也难，但无单向函数 | 最糟的世界：难题解不了，也换不来密码学 |
| Minicrypt | 单向函数存在，但无公钥密码 | 有对称加密与签名，无法与陌生人建立密钥 |
| Cryptomania | 公钥密码存在 | 我们以为自己所在的世界 |
这个框架的价值在于它把一堆分散的开放问题排成了一条线：每两个相邻世界之间的分隔，都对应一个具体的、悬而未决的数学问题。而我们连自己在哪个世界都不知道——现代信息基础设施建立在"我们在 Cryptomania"这一未经证明的信念之上。
Pessiland 尤其值得停一下。 在那个世界里，困难是真实的却毫无用处：你既无法解出难题，也无法把它的难度转化成任何有价值的东西（如加密）。它提醒我们，"困难"本身不是资源——只有当困难可以被制造、被验证、且带有陷门时，它才变成资源。
Heuristica 也不轻松。在那里，难实例存在但稀少而病态：算法在绝大多数输入上表现良好，却会在少数实例上灾难性地失败，而且你事先无法辨认哪些实例是灾难。排除 Heuristica——证明某个 NP 问题在自然的分布上也难——恰恰是第四节最坏—平均归约想做而没能做成的事。
五个世界之间还有一类已经证明的"墙"。1989 年，Impagliazzo 与 Rudich 证明：不存在把单向置换黑盒地升级为密钥协商协议的构造——相对于一个随机谕示，单向置换存在而公钥密钥协商不存在。这个结果不排除非黑盒技术，但它解释了此后三十多年的事实：所有成功的公钥构造都来自具体的代数结构（因式分解、离散对数、椭圆曲线、格），没有一个是任意单向函数的纯黑盒产物。Minicrypt 与 Cryptomania 之间的那道墙之所以至今推不倒，部分原因是我们最好的通用构造技术被证明推不倒它。
四、最坏—平均归约：桥能不能架起来
一个自然的希望是：能否证明"若最坏情况难，则平均情况也难"？对某些问题可以。
- 离散对数与格问题：格上的若干问题具有最坏—平均归约——Ajtai 1996 年开创了这条路线，Regev 对带错学习（LWE）给出的归约把随机实例的难度锚定在格问题的最坏情况难度上。这正是基于格的后量子密码方案在理论上更受青睐的根本原因：它的安全性有更强的形式支撑。需要诚实说明的是，Regev 的归约是量子归约——把 LWE 的困难归约到格问题的量子算法；纯经典的归约至今仍是开放问题。
- 对一般 NP 问题则相反：Feigenbaum 与 Fortnow 1993 年首先揭示了这类归约的内在局限；Bogdanov 与 Trevisan 随后证明，用非适应性归约把 NP 完全问题的最坏情况困难转化为平均情况困难，会迫使 coNP 拥有非确定性的多项式规模电路，从而令多项式层级坍缩——学界普遍不相信这一后果成立。这构成了另一道障碍，与 P vs NP 的三道障碍属于同一族现象。
因此当前的图景是：桥在少数结构丰富的问题（格、编码）上架得起来，而对一般情况，我们有理由相信它架不起来。这就是为什么现代密码学的安全性总是建立在具体问题（因式分解、离散对数、格）之上，而不是建立在 NP 完全性之上——尽管后者听起来更有力。
还有一条更经验主义的通道值得一提。随机 3-SAT 在特定的子句—变量密度区间内在实践中极难解；Goldreich 曾提议直接以"随机局部函数求逆"作为单向函数候选，其安全性完全依赖经验与二十年未被动摇的密码分析记录，而非任何归约。这类"种植式"构造（把隐藏结构埋进随机实例）如今广泛用于密码学与统计推断的交叉地带——它没有定理背书，却是平均情况难度假设进入工程设计的真实路径，其风险也正是本节标题所暗示的：没有最坏情况锚点的困难，只能靠持续的攻击来检验。
五、元复杂性：把"难"本身当作计算问题
近年最活跃的进展来自一个自指的转向：判断一个字符串有多难压缩、判断一个函数需要多大电路——这些问题本身有多难？
最小电路规模问题（MCSP）是代表：给定一个函数的真值表与一个数 $s$，判断它能否被规模 $s$ 的电路计算。它的复杂性状态至今未知——既没有被证明是 NP 完全的，也没有被证明属于 P。它卡在一个微妙的位置上：若它太容易，就能充当"自然性质"去击破伪随机性；若它足够难，它本身就是密码学的候选材料。它恰好坐在自然证明障碍的边界上，两边都容不下一个平凡的答案。
它之所以关键，是因为已有一批结果把它与单向函数的存在性联系起来。2020 年，刘彦毅（Yanyi Liu）与 Rafael Pass 证明了这个方向的标志性定理：单向函数存在，当且仅当时间有界的柯氏复杂度问题在均匀分布上具有温和的平均情况难度。 也就是说，"我们生活在 Minicrypt 还是更差的世界"这个问题，被翻译成了一个关于具体字符串问题的、完全组合化的问题——而这正是自然证明障碍所关心的对象。此后这条线迅速发展：等价性被推广到列文式柯氏复杂度（同时计入程序长度与运行时间）等多个变体，并且由于单向函数存在本身就要求 P ≠ NP，这些结果同时意味着——只要密码学是可能的，这些元问题的平均情况难度就成立，排除 Heuristica 与 Pessiland 的工作因此全部汇流到了元复杂性上。
这一步的深意在于方向的倒转：过去人们试图用复杂性假设支撑密码学；现在，密码学的存在性本身被刻画为一类元问题的平均情况难度。把障碍本身变成研究对象，是当前最被看好的绕过它的路径——列文 1986 年埋下的"问题加分布"框架，在三十多年后成了打通两个领域的公共语言。
跨域连接
- 哥德尔不完备定理：柯氏复杂度与不完备性有一条直接联系——任何足够强的形式系统只能证明有限多个字符串的复杂度下界（柴廷的论证）；这与"我们无法证明具体问题难"的处境同源，也提示元复杂性的困难可能有比技术障碍更深的根子。
- 概率论：平均情况的整个概念依赖于对输入分布的建模——"自然出现的实例服从什么分布"是一个无法从数学内部回答的问题，而它决定了难度结论是否适用于现实；这解释了为什么 NP 完全问题在实践中常常可解：真实实例的分布远比最坏情况友善，而这不是理论的失败，是理论从未承诺过的东西。
- 后量子密码：格问题的最坏—平均归约是它最重要的理论卖点——它让"随机生成的密钥是安全的"这一实践需求获得了形式保证，而基于因式分解的方案没有同等强度的支撑；这条理论优势与抗量子性是两件独立的事，实践中却常被混为一谈。
- 统计学习理论与 PAC 学习：可学习性与密码学在形式上互为镜像——一个函数类如果可以被高效学习，就不能用来构造伪随机函数；反过来，单向函数的存在直接给出了机器学习的困难性结果；这意味着"什么学不会"与"什么可以用来加密"是同一个问题的两种问法。
- 市场失灵与公共物品：整个数字经济的信任基础建立在一组未被证明的猜想上——这是一种特殊的公共品：其可靠性由全球密码学界的持续攻击检验来维护，而没有任何单一主体有动机为这种检验付费；后量子迁移的缓慢正说明了这类公共品在缺乏协调时的典型困境。
参考文献
- Levin, Leonid A. "Average Case Complete Problems." SIAM Journal on Computing, vol. 15, no. 1, 1986, pp. 285–286.
- Impagliazzo, Russell. "A Personal View of Average-Case Complexity." Proceedings of the 10th Annual Structure in Complexity Theory Conference, 1995, pp. 134–147.
- Bogdanov, Andrej, and Luca Trevisan. "Average-Case Complexity." Foundations and Trends in Theoretical Computer Science, vol. 2, no. 1, 2006, pp. 1–106.
- Håstad, Johan, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. "A Pseudorandom Generator from Any One-Way Function." SIAM Journal on Computing, vol. 28, no. 4, 1999, pp. 1364–1396.
- Regev, Oded. "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography." Journal of the ACM, vol. 56, no. 6, 2009, article 34.
- Goldreich, Oded, and Leonid A. Levin. "A Hard-Core Predicate for All One-Way Functions." Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989, pp. 25–32.
- Impagliazzo, Russell, and Steven Rudich. "Limits on the Provable Consequences of One-Way Permutations." Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989, pp. 44–61.
- Feigenbaum, Joan, and Lance Fortnow. "Random-Self-Reducibility of Complete Sets." SIAM Journal on Computing, vol. 22, no. 5, 1993, pp. 994–1005.
- Bogdanov, Andrej, and Luca Trevisan. "On Worst-Case to Average-Case Reductions for NP Problems." SIAM Journal on Computing, vol. 36, no. 4, 2006, pp. 1119–1159.
- Liu, Yanyi, and Rafael Pass. "On One-way Functions and Kolmogorov Complexity." Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS), 2020.
延伸阅读
- Goldreich, Oded. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008.
- Arora, Sanjeev, and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009（第 18 章）.
- Barak, Boaz. An Intensive Introduction to Cryptography. 讲义, Harvard University（持续更新）.