大多数关于 P 与 NP 的介绍会告诉你问题是什么、悬赏多少、以及"大家都相信 P ≠ NP"。很少有介绍讲这件事：我们不只是没证出来，我们还知道为什么整类看起来最自然的证明方法注定证不出来。
这三道被称为障碍的结果，是复杂性理论最独特的贡献之一——一门学科系统地研究自己的证明方法为何失效，并把结论写成定理。 它们让 P vs NP 从"一个很难的问题"变成了"一个我们知道需要什么样的新工具才能解决的问题"。
破除误解
第一个误解：以为障碍说明这个问题不可解。 它们不是不可判定性结果。每一道障碍排除的都是一类具体的证明技术，而不是所有可能的证明。 事实上，每道障碍出现之后，都有证明成功地绕过了它——IP = PSPACE 绕过了相对化，威廉斯的 NEXP 对 ACC 下界后来同时绕过了全部三道——只是尚未走到最终目标。绕行记录的存在，恰恰是障碍框架有预测力的证据。
第二个误解：以为"P ≠ NP 显然为真，只是难写下来"。 直觉的强度不能代替证明。更重要的是：如果它显然为真，为什么三类最有力的通用技术全部失效？ 障碍的存在本身就在提示，这个命题的真相与我们的直觉之间可能隔着某种结构性的东西。
第三个误解：以为这只与理论家有关。 现代密码学的安全性建立在"某些问题没有高效算法"之上。而我们连 P ≠ NP 都无法证明，这意味着整个密码学体系建立在一组未被证明的假设上——障碍解释了这种状况为什么在可预见的将来不会改变。
一、第一道：相对化（1975）
早期最自然的想法是套用图灵的对角化——那套技术曾漂亮地证明了停机问题不可判定，也被哈特马尼斯与斯特恩斯（Hartmanis 与 Stearns）在 1965 年用来证明时间层级定理（给图灵机更多时间，它确实能计算更多函数）。对角化的战绩如此辉煌，以至于 P vs NP 看起来只是"再找一个更精巧的自我指涉构造"的问题。
贝克、吉尔与索洛维在 1975 年封死了这条路。他们构造了两个神谕（一个可以被免费查询的黑箱）：
- 存在神谕 $A$，使得 ；
- 存在神谕 $B$，使得 。
关键在于：对角化这类技术是"相对化"的——它们把机器当作黑箱操作，只依赖输入输出行为，因而在加上任何神谕后同样有效。既然加不同神谕会得到相反的答案，任何相对化的证明就不可能确定无神谕世界里的真相。 换句话说，对角化无法区分"计算本身"与"计算加上一个免费黑箱"，而 P vs NP 的答案偏偏依赖于这一区分。
这一步的哲学含义值得停一下：它说明 P vs NP 的答案必须依赖于计算的内部结构（电路长什么样、门怎么连），而不能只依赖于"输入输出行为"这一层。问题的难点第一次被定位了。 这道障碍还有一个常被忽略的实用读法：它同时提供了一个过滤器——任何证明路线，只要它是相对化的，就可以立刻被排除，不必逐行检查。证明技术本身从此成了被分类、被判定适用范围的对象，这是复杂性理论区别于多数数学分支的一点。
二、第二道：自然证明（1994/1997）
绕开相对化的自然方向是电路复杂性：不把程序当黑箱，而是直接证明"任何计算某函数的电路都必须很大"。这条路在 1980 年代取得了真实进展：弗斯特、萨克斯与西普塞尔（Furst、Saxe 与 Sipser）证明了常深度电路计算奇偶性需要指数规模；拉兹博罗夫 1985 年证明单调电路判定团问题需要指数规模；斯莫伦斯基（Smolensky）1987 年把这些下界推广到带模门的电路。指数下界第一次看起来触手可及，当时普遍的乐观是：剩下的只是技术爬坡。
拉兹博罗夫与鲁迪奇在 1994 年（1997 年正式发表）指出了一个惊人的自我妨碍。他们把当时几乎所有已知的下界证明抽象成一个共同模式，称为自然证明，它有两个性质：
- 构造性：给定函数的真值表，可以高效地判断它是否具有"难"的那个性质；
- 广泛性：随机函数以不可忽略的概率具有该性质。
然后是那个转折：如果存在这样一个自然性质能证明 P ≠ NP，就可以用它高效地区分伪随机函数与真随机函数——而这等于攻破了伪随机函数生成器，也就等于攻破了单向函数。
于是得到一个近乎悖论的结论：
如果单向函数存在（这正是我们相信 P ≠ NP 的主要理由之一），那么就不存在证明 P ≠ NP 的自然证明。
我们相信这个命题为真的理由，恰恰阻止了我们用最顺手的方法证明它。 这在数学史上都罕见——一个猜想的可信度来源同时是它的证明障碍。
自然证明框架同时给出了逃逸条件的清单：一个能证 P ≠ NP 的性质必须不可高效检验，或者不被随机函数广泛满足。后一条路线的一个化身是几何复杂性理论；前一条则指向那些只针对特定函数的、非黑箱的论证。障碍没有说"放弃"，它说的是"往这两个方向找"。
三、第三道：代数化（2008）
IP = PSPACE 是如何绕过相对化的？1990 年，伦德、福特诺、卡洛夫与尼桑（Lund、Fortnow、Karloff 与 Nisan）为计数问题 #P 构造了交互式证明，沙米尔（Shamir）随即用同样的技术证明 IP = PSPACE；不久之后 PCP 定理问世。这些证明靠算术化：把布尔公式提升成有限域上的多项式，从而利用代数结构——它们处理的是公式的代数形态，而不是黑箱机器的输入输出行为，因此天然不相对化。这条路一度看起来是突破口——PCP 定理随后表明，任何 NP 证明都可以改写成"只抽查常数个位置便以大概率可信"的形式，算术化的威力还在扩大。
阿伦森与维格森在 2008 年证明它同样有边界。他们把神谕的概念推广为代数神谕（不仅能查询布尔函数，还能查询它的低次多项式扩展），并证明：存在代数神谕使 P = NP，也存在代数神谕使 P ≠ NP。
由于算术化技术会"代数化"，它同样无法单独解决 P vs NP。至此，三道障碍分别封死了三代主流技术：对角化、组合式电路下界、代数化。
值得留意这道障碍留下的出口有多精确：要逃逸，证明必须使用超出低次多项式扩展所能表达的结构。这个条件具体到后来研究者可以逐条检查一项新技术是否满足。从"某类方法不行"到"要行就必须满足某个性质"，障碍越到后期越像一张工程规格书。
| 障碍 | 年份 | 封死的技术 | 逃逸的条件 |
|---|---|---|---|
| 相对化 | 1975 | 对角化 / 模拟 | 必须利用计算的内部结构 |
| 自然证明 | 1997 | 组合式电路下界 | 性质必须不构造性或不广泛 |
| 代数化 | 2008 | 算术化 / 多项式扩展 | 必须超出低次多项式扩展所能表达的范围 |
四、人们正在尝试什么
几何复杂性理论（穆利穆尼与索恩）试图把复杂性下界转化为代数几何与表示论中的问题，寻找区分不同复杂类的"表示论障碍"。它明确地非构造性，因而不属于自然证明的范畴——代价是所需的数学工具极其深，进展缓慢，且近年若干关键的猜想被证否：穆利穆尼的强饱和猜想 2009 年被布里安、奥雷利亚纳与罗萨斯（Briand、Orellana 与 Rosas）证否；2019 年比尔吉瑟、伊肯迈尔与帕诺娃（Bürgisser、Ikenmeyer 与 Panova）进一步证明，用"出现障碍"（occurrence obstruction）分离行列式与永久式在原则上行不通，障碍对象必须携带重数信息——这把 GCT 的工具箱削去了一块，迫使路线本身被修正。
元复杂性近年成为最活跃的方向：研究"判断一个字符串的复杂度"这类问题本身的复杂性（如最小电路规模问题 MCSP）。它的吸引力在于自然证明障碍恰恰是关于这类问题的——把障碍本身当作研究对象，可能是绕过它的方式。2020 年刘与帕斯（Liu 与 Pass）证明了一个标志性等价：单向函数存在，当且仅当时间有界的柯尔莫哥洛夫复杂度问题是平均情况困难的。这第一次把密码学最核心的假设与一个具体的元复杂性问题完全画上等号——它不是绕过障碍，而是把障碍翻译成另一个领域里的精确问题，让两边的工具得以互相进入。
还有一条路线干脆同时绕开全部三道障碍。威廉斯（Ryan Williams）2011 年证明 NEXP 不包含于多项式规模的 ACC 电路，方法是一个此前被忽视的组合：先为这类电路设计一个略快于穷举的可满足性算法，再由此推出电路下界——"算法推出下界"。这个证明利用具体函数的内部结构（不相对化），不给出广泛性质（不自然），并使用了超出低次多项式扩展的构造（不代数化）。它离 P ≠ NP 还很远——NEXP 比 NP 大得多——但它是第一个同时避开三道障碍的非平凡电路下界，证明了三道障碍留下的缝隙虽然窄，确实存在。
部分战果是真实的：受限电路类（常深度电路、单调电路）的指数下界成立且已绕过所有三道障碍；时间—空间权衡一侧，也已证明 SAT 无法在只用亚线性空间的同时保持近线性时间；若干"P ≠ NP 的弱化版本"同样已证。领域并未停滞，只是最终目标所需的工具还没被发明。
五、这件事教给我们什么
障碍研究本身是一种成熟的标志。 一门学科能证明"我现有的方法不足以解决这个问题"，比一门不断宣布突破又不断撤回的学科更可靠。它把大量精力从注定失败的方向引开——每年提交的 P vs NP "证明"中，绝大多数在与三道障碍对照时几秒钟内就能被排除，因为它们使用的正是被证明无效的技术。
障碍还澄清了"相信 P ≠ NP"这句话内部的分层。 因帕利亚佐（Impagliazzo）1995 年把"P ≠ NP 之后的世界"细分成五种可能：从"NP 完全问题在平均情况下也容易"的世界，到"单向函数存在、密码学可以立足"的世界。今天的主流押注偏向密码学可行的那一侧，但五种世界没有一种被排除——而三道障碍说明的正是：在证明层面，我们连最弱的那种排除都还做不到。
它也给出了一个关于知识的一般教训：当一个问题长期抵抗最优秀的头脑，值得追问的不只是"答案是什么"，还有"我们的工具在结构上缺了什么"。后一个问题往往更容易取得进展，而且它的答案会重塑整个领域的地图。 物理学的以太漂移实验、数论中费马大定理的三个世纪，走的都是这条路——"证明我们现有的证明不够格"本身就是一种知识增量，而且往往是通向真正突破的那一级台阶。
跨域连接
- 哥德尔不完备定理：两者都是关于证明能力本身的限制，但性质不同——哥德尔说的是某些真命题在给定形式系统内不可证，障碍说的是某些技术无法证明某个特定命题；后者更弱也更实用：它不排除更强的方法存在，只是把搜索空间大幅缩小；把二者混为一谈会得出"P vs NP 可能不可判定"这一并无充分依据的结论。
- 概率论：自然证明障碍的核心是一个概率论断言——"随机函数几乎必然具有该性质"这条广泛性要求，正是它可以被用作区分器的原因；伪随机性的整个理论建立在"计算受限的观察者无法区分"这一概念上，而它与统计意义上的随机性是两个不同的东西，这一区分是理解这道障碍的钥匙。
- 密码学基础：现代密码学的全部安全性都是条件性的——它假设某些问题困难，而障碍解释了为什么这些假设在可预见的将来无法被证明；这带来一个常被忽视的推论：密码学不是"建立在数学证明之上"的学科，而是建立在一组经受了长期攻击考验的猜想之上，其可信度更接近实验科学而非纯数学。
- P 与 NP 问题：数学界把它列为千禧年七大难题之一，而障碍解释了这个悬赏为何多年无人认领——问题的陈述极其简单，可用的工具却被系统性地排除；这也是判别民间"证明"最有效的筛子：先问它属于哪一类技术，再对照三道障碍，绝大多数在这一步就出局，而不必逐行阅读。
- 我们能知道什么？：这是认识论问题的一个精确化版本——复杂性理论不满足于说"我们还不知道"，而是把"为什么用现有方法不可能知道"证明成了定理；对照多数领域用"还需要更多研究"来处理无知，这是一种更高标准的诚实，也提供了一个可迁移的方法：先追问工具在结构上缺了什么，再追问答案是什么。
参考文献
- Baker, Theodore, John Gill, and Robert Solovay. "Relativizations of the P =? NP Question." SIAM Journal on Computing, vol. 4, no. 4, 1975, pp. 431–442.
- Hartmanis, Juris, and Richard E. Stearns. "On the Computational Complexity of Algorithms." Transactions of the American Mathematical Society, vol. 117, 1965, pp. 285–306.
- Shamir, Adi. "IP = PSPACE." Journal of the ACM, vol. 39, no. 4, 1992, pp. 869–877.
- Razborov, Alexander A., and Steven Rudich. "Natural Proofs." Journal of Computer and System Sciences, vol. 55, no. 1, 1997, pp. 24–35.
- Aaronson, Scott, and Avi Wigderson. "Algebrization: A New Barrier in Complexity Theory." ACM Transactions on Computation Theory, vol. 1, no. 1, 2009, article 2.
- Williams, Ryan. "Nonuniform ACC Circuit Lower Bounds." Journal of the ACM, vol. 61, no. 1, 2014, pp. 1–32.
- Liu, Yanyi, and Rafael Pass. "On One-way Functions and Kolmogorov Complexity." Proceedings of the 61st IEEE Symposium on Foundations of Computer Science (FOCS), 2020.
- Impagliazzo, Russell. "A Personal View of Average-Case Complexity." Proceedings of the 10th Annual Structure in Complexity Theory Conference, 1995.
- Bürgisser, Peter, Christian Ikenmeyer, and Greta Panova. "No Occurrence Obstructions in Geometric Complexity Theory." Journal of the AMS, vol. 32, no. 1, 2019, pp. 163–193.
- Mulmuley, Ketan D., and Milind Sohoni. "Geometric Complexity Theory I: An Approach to the P vs. NP and Related Problems." SIAM Journal on Computing, vol. 31, no. 2, 2001, pp. 496–526.
- Aaronson, Scott. "P =? NP." In Open Problems in Mathematics, Springer, 2016, pp. 1–122.
延伸阅读
- Arora, Sanjeev, and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009（第 3、23 章）.
- Wigderson, Avi. Mathematics and Computation. Princeton University Press, 2019.
- Fortnow, Lance. The Golden Ticket: P, NP, and the Search for the Impossible. Princeton University Press, 2013.