注明题目难以办理究竟有多难？元复杂性（meta-complexity）实践研讨者数十年来一直探究这个题目。近期的一系列研讨成果开始给出这个题目的答案。复杂性实践研讨者正直面着最让人困惑的题目：复杂性实践本身。
一、起源
2007 年秋季学期的第一周，Marco Carmosino 拖着自己去上了一堂数学课，这是马萨诸塞大学阿默斯特分校估计机科学专业学生的必修课。Carmosino 是一位大二学生，他当时正在考虑退学去设计视频游戏游戏。上课的教授提出了一个简单的题目，而这个题目将改变他的人生轨迹：你怎么知道数学真的有用？
「这让我坐正了身体开始用心听讲。」Carmosino 回忆说，他现在是 IBM 的一位实践估计机科学家。他报名参加了一个选修的讲库尔特・哥德尔（Kurt Gödel）的工作的讲座。哥德尔那让人头晕目眩的自我指涉论证第一次揭示了数学推理的局限性并为估计的基本局限性方面的所有未来研讨工作奠定了基础。其中涉及了太多过于艰难的概念。
「我完全无法理解，」Carmosino 说，「但我知道我希望能理解。」
现如今，即使是经验丰富的研讨者，在面对实践估计机科学领域核心的那个至今未被办理的题目时，也依然会感觉难以理解。这个题目就是著名的 P 与 NP 题目。从本质上讲，这个题目问的是：许多长久以来都被认为极其困难的估计题目是否实际上都可以轻松办理（通过一条我们尚未发现的秘密捷径），还是说是否就像大多数研讨者猜测的那样，难题恒难？这个题目可以说就是可知事物的本质。
尽管估计复杂性实践（研讨的是不同题目的内在难度）领域的研讨者们已经付出了数十年的艰辛努力，但 P 与 NP 题目的答案依然遥遥无期。我们甚至都不知道能够的注明应该从哪里开始。
「这里没有路线图。」Michael Sipser 说，他是麻省理工学院（MIT）一位资深的复杂性实践研讨专家，曾在 1980 年代耗费了数年时间与这个题目搏斗。「就好像是你进入了荒野之中。」
看起来，注明估计题目难以办理本身就是一个难题。但为什么这个题目会这么难？而且这个题目究竟有多难？Carmosino 等研讨元复杂性（meta-complexity）子领域的研讨者研讨的是将这样的题目重新表述为估计题目，通过将复杂性实践的透镜转向自身来推动这一领域向前发展。
「你能够会想：哇，那挺酷的呀。也许这些复杂性实践研讨者都疯了。」MIT 一位研讨生 Rahul Ilango 说，他得到了该领域一些近期最为激动人心的成果。
通过研讨这些内向型题目，研讨人员了解到：注明估计难度这一任务的难度与一些初看好像无关的基本题目密切相关。发现看似随机的数据中的隐藏模式有多难？如果确实消失真正困难的题目，那么题目困难的能够性有多大？
「元复杂性接近事物的核心，这越来越明显了。」Scott Aaronson 说，他是德克萨斯州大学奥斯汀分校一位复杂性实践研讨者。
这是引领研讨者从 P 与 NP 题目迈向元复杂性的漫长而曲折的故事。这并不是一段轻松的旅程 —— 道路上布满了错误的转弯和路障，而且它还一次又一次地循环回到自身。然而，对元复杂性研讨者来说，进入未知疆域的旅程本身就是一种奖励。加拿大西蒙菲莎大学的复杂性实践研讨者 Valentine Kabanets 说：从提出看似简单的题目开始，「你完全不知道会走向何方。」
已知的未知
「P 与 NP 题目」这个听起来枯燥无味的名称来自复杂性实践研讨者们的习惯 —— 他们习惯把估计题目分类成宽泛的「复杂性类（complexity class）」，然后给它们打上类似纳斯达克股票代码的标签。估计题目是指原则上可通过算法办理的题目，而算法则是指精确指定的指令列表。但是，并不是所有算法的用处都一样大，算法之间的差异暗示着不同类的题目之间的根本性差异。复杂性实践研讨者面临的挑战是将这些暗示变成有关复杂性类之间的关系的严格定理。
这些关系反映了关于估计的永恒不变的真理，其远远超越了任何具体的技术。Kabanets 说：「这就像是发现宇宙定律。」
在数量不断变多的几百个复杂性类中，「P」和「NP」是其中最著名的两个。粗略地说，P 是一类很容易求解的题目，比如按字母顺序排列一个列表。NP 这一类则是有容易检验的解的题目，比如数独解密。由于所有容易求解的题目都容易检验，所以 P 中的题目也都属于 NP。但某些 NP 题目似乎难以办理 —— 你无法直接靠直觉就填满一个数独，而是需要先尝试许多能够性。有没有能够这种表面上的困难只是一种假象 —— 其实消失某种简单的技巧可以求解每个易于检验的题目？
展示复杂性类 P 与 NP 之间的关系的维恩图。
如果是那样，那么 P = NP：这两个类等价。如果是这种状况，那么必然消失某种算法可以极大简化大规模数独求解、优化全球航线、破解最先进的加密技术以及自动注明数学定理等题目。如果 P ≠ NP，则许多原理上可以办理的估计题目实际上将永远无法办理。
早在 P 与 NP 题目首次被提出之前很久，研讨者们就已经在担忧形式化数学推理的局限性了 —— 事实上，这比现代估计机科学的诞生还要早得多。1921 年，那是在同一题目吸引了 Carmosino 的注意力的一个时间之前，数学家大卫・希尔伯特提出了一个研讨计划，希望将数学建立在绝对确定性的基础上。他希望从一些简单的假设（公理）开始，推导出一套满足三大关键标准的统一的数学实践。
希尔伯特的第一个条件是一致性（consistency），这是一项基本要求，即数学必须没有矛盾：如果可以基于同样的公理注明出两个相互矛盾的陈述，那么这整个实践都是无可救药的。但一个实践可以既没有矛盾，也消失局限。这就涉及到希尔伯特的第二个条件了：齐备性（completeness）：其要求所有数学陈述要么可注明为真，要么可注明为假。他的第三个标准是可判定性（decidability），即要求有一个无歧义的机械流程来判定任何数学陈述是真还是假。在 1930 年的一次会议上，希尔伯特宣告说：「我们的口号应该是：『我们必定知道，我们必将知道。』」
仅仅一年后，哥德尔就给希尔伯特的梦想带来了第一次打击。他注明「本陈述是不可注明的」这样的自我推翻（self-defeating）陈述可从任何适当的公理集推导出来。如果这样一个陈述确实是不可注明的，那么该实践就不是齐备的；如果它是可注明的，那么该实践就是不一致的 —— 这个结果更糟糕。哥德尔还在同一篇论文中注明：任何数学实践都无法注明其自身的一致性。
大卫・希尔伯特、库尔特・哥德尔和阿兰・图灵身着正装的黑白照片。1920 年代，大卫・希尔伯特（左）希望让数学有更加坚实的基础。库尔特・哥德尔和阿兰・图灵后来注明希尔伯特的梦想无法实现。
研讨者仍旧抱有希望：未来的某个数学实践能够不一定是齐备的，但能够却能被注明是可判定的。也许他们可以开发出一些工作流程，能够在识别出所有可注明陈述的同时避开哥德尔提出的那样的让人恼火的命题。题目是没人知道如何推理得到这些假设消失的工作流程。
然后在 1936 年，一位名叫阿兰・图灵的 23 岁研讨生以当时人还不熟悉的估计领域的语言重新表述了希尔伯特的可判定性条件，并给了它致命一击。图灵构建了一个数学模型（被称为图灵机），它可以表示所有能够的算法；而图灵在论文《On Computable Numbers, with an Application to the Entscheidungsproblem》中注明如果希尔伯特方案确实消失，那么它就符合这个模型。然后他使用了类似哥德尔要领的自我指涉要领注明不可判定的陈述确实消失 —— 等价来说：任何算法都无法办理的不可估计题目。
希尔伯特计划轰然坍塌：对于什么可以注明，什么可以估计，永远消失根本性的限制。但随着估计机从实践抽象变成真实的机器，研讨者们认识到图灵对可解题目和不可解题目的简单区分留下了许多有待解答的题目。
到 1960 年代，估计机科学家已经开发出了能快速求解一些题目的算法，尽管在其他人看来，已知的算法都慢得让人头痛。但要是题目的关键不是题目是否可解，而是求解它们的难度有多大呢？
「一个丰富的实践出现了，而我们已经不知道答案了。」Carmosino 说。
分叉的道路
为了阐释难度题目是多么地令人困惑，让我们来看看两个涉及图（graph）的紧密相关的题目。图是由点（称为节点）和线（称为边）构成的网络。估计机科学家使用图来建模各种各样的东西，从量子估计到交通状况。
在含 12 个节点的图上的哈密顿门路。
哈密顿门路是指通过每个节点一次的门路。从原理上讲，这个题目明显是可解的：因为能够门路的数量是有限的，所以就算其它要领都不行，你也可以直接检验每一条门路。如果节点的数量很少，这没什么题目，但只要图的规模稍大一些，能够性的数量就会暴增到失控程度，让这种简单要领难以为继。
有一些更复杂的哈密顿门路算法能更好地办理题目，但算法办理题目所需的时间总是会随图的大小呈指数增长。图不一定要非常大，最优秀的算法研讨者能够就已经发现无法找到这样的门路了，至少是无法「在任意合理的时间内」。加利福尼亚大学圣迭戈分校复杂性实践研讨者 Russell Impagliazzo 这样说，「我说的『合理的时间』是指『在宇宙毁灭之前』。」
哈密顿门路题目还有一个有趣的性质。如果有人宣称找到了某个图的哈密顿门路，那么你可以快速检验这个解是否有效；即使这个图很大，检查起来也很容易。你只需要跟随该门路，一个接一个地勾选节点，然后检查并确保你不会两次勾选某个节点。如果最后你也没有错过任何节点，那么该门路便是哈密顿门路。
指数级算法和多项式算法的增长趋势。
运行这个检验解的算法所需的时间与图的大小成正比。这类算法属于一个更宽泛的算法类别：多项式算法；其运行时间的增长是图大小的多项式函数。相比于指数级增长，多项式增长的速度较为平缓，因此即使是很大的图，多项式算法也依然可行。Carmosino 说：「它的效率要高得多。」
在含 12 个节点的图上的欧拉门路。
哈密顿门路题目具有明显的不对称性：你可以使用一个快速的多项式算法检验一个解是否正确，但却需要指数级算法才能找到一个解。这种不对称性能够并不出人意料，毕竟欣赏一件艺术杰作比创作一件艺术杰作更容易，检验一个数学注明也比注明一个新定理更容易，然而并非所有估计题目都具有这样的不对称性质。事实上，就消失一个与寻找哈密顿门路题目非常相似但行为表现大相径庭的题目。
同样假设你有一个图，但你要做的是找到一条「欧拉门路」，即穿过每条边刚好一次的门路。同样，在检验能够的解方面，消失多项式算法，但求解这个题目也消失一个多项式算法。这里就没有不对称性。在复杂性实践中，某些门路似乎比其它门路更容易找到。
哈密顿门路题目和欧拉门路题目都属于复杂性类 NP，其定义包括所有可用多项式算法检验解的题目。欧拉门路题目也属于 P 类，因为可用一个多项式算法求解它，但目前来看哈密顿门路题目并非如此。为什么这两个图题目表面上如此相似，实际却又如此不同呢？这就是 P 与 NP 题目的本质所在。
普遍困难
一开始的时候，复杂性类看起来是很方便的分类要领，可以把相似但不直接相关的题目归类到一起 —— 之前没人想到寻找哈密顿门路与其它困难的估计题目有关。
然后到了 1971 年，在被美国拒绝终身教职而转到多伦多大学后不到一年，复杂性实践研讨者史蒂芬・库克（Stephen Cook）发表一项非凡的研讨成果《The complexity of theorem-proving procedures》。他发现有一个特殊的 NP 题目有一个奇怪的特征：如果有一种多项式算法能办理这个题目，那么该算法也能办理 NP 类中的所有其它题目。库克的「普适」题目似乎是支撑看似困难的题目类别的一根孤柱，将它们与简单题目分开了。只需办理那一个题目，其它 NP 题目都会迎刃而解。
身着羊毛背心的史蒂芬・库克坐在一张桌子前。史蒂芬・库克与莱昂尼德・列文和理查德・卡普一起在 1970 年代形式地描述了 P 与 NP 题目。
库克怀疑世上根本就不消失针对他的普适题目的快速算法，他在那篇论文中间如此说到，并且还补充说：「我觉得投入相当大的努力去注明这个猜想是值得的。」事实注明，「相当大的努力」还是低估了。
大约同一时期，苏联一位名为莱昂尼德・列文（Leonid Levin）的研讨生在论文《Universal Sequential Search Problems》中注明得出了相似的结论，不过他还发现了几个不同的普适题目。此外，美国的复杂性实践研讨者理查德・卡普（Richard Karp）通过论文《Reducibility among Combinatorial Problems》注明库克发现的普适性本身就几乎是普适的（其实列文发现的普适性也一样，只不过卡普和库克要多年之后才知道列文的研讨成果）。几乎所有没有已知多项式算法的 NP 题目都有这样的性质，即几乎每个可以轻松检验的题目看起来都很难。这后来被称为 NP 齐备性（NP-completeness）。
这意味着哈密顿门路题目和数独等所有 NP 齐备题目在某个精确的意义上都是等价的。「这些不同的当然任务有很多，而它们全都神奇地变成了同一个任务。」Ilango 说，「而我们仍然不知道是否能够办理这个任务。」
确定任何 NP 齐备题目的难度就足以办理 P 与 NP 题目。如果 P ≠ NP，则难易题目之间的界限就由数千个同样坚固的柱子支撑着。如果 P = NP，则这整座大厦就已经濒临崩塌，只等一块碎片落下。
用维恩图表示 P 与 NP 齐备题目中的题目。
库克、列文和卡普将许多看似不相关的题目统一了起来。现在，所有复杂性实践研讨者要做的就是办理这个题目：P = NP 是否成立？
五十年后，这个题目依然没能得到解答。Kabanets 将对数学局限性的推理比作是探索一片全局状况未知的巨大疆域。一个拥有无限估计力的消失可以从最高的山顶俯瞰全局，一眼洞悉整个图景，但普通的凡人不能指望获得这种优势。他说：「我们这些山脚下的人也许可以试着上跳下窜，获得一个更好的视野。」
假设 P = NP 成立。为了注明这一点，研讨者需要找到一个用于 NP 齐备题目的快速算法，这个算法能够隐藏在那个巨大图景中某个不起眼的角落。谁也不能保证他们能很快找到它：复杂性实践研讨者在经过几十年的工作后偶尔会发现一些用于看似很难（尽管不是 NP 齐备）的题目的精妙算法。
现在假设 P ≠ NP。注明这一点还要更难。复杂性实践研讨者必须注明不能够消失任何快速算法，这个任务的难度实在太大，实际上挫败了未来所有研讨者。
一大难点是研讨者们根本不知道从哪里开始。但也不是说没有研讨者尝试。过去几十年来，他们从不同角度向这个题目发起过冲击，但没一次都发现前进之路已被堵塞。「这是实践估计机科学领域最明显不过的事实之一。」Carmosino 说，「当面对一个如此持久的现象时，你肯定想获得一些解释。」
二、故障
在 Carmosino 上大学的最后一年，他的好奇心将他从哥德尔引向了复杂性实践的研讨生课程。他惊讶地发现自己在作业上花费的时间多于在其激情项目上投入的时间 —— 这个项目是一个能学习童话故事的叙事结构并生成新故事的估计机程序。
Carmosino 回忆说：「那时候我想：哇，我得认真对待这个题目。」没过多久，他就对这门学科产生了浓厚的兴趣，以至于他的导师都细心地建议他重新考虑毕业后的计划。
「他说：你知道，如果你想继续做这个，如果你想继续研讨实践估计机科学和复杂性实践，你可以继续：这叫做研讨生学校。」Carmosino 说。获得硕士学位后，他于 2012 年来到圣地亚哥，在 Impagliazzo 的指导下攻读博士学位。
Marco Carmosino 身着蓝色衬衫和西装外套的照片。Marco Carmosino 在 1980 年代对一个重大成果的痴迷给他带来了灵感，让他在 20 年后为元复杂性领域带来了突破。
Carmosino 一开始的主要目标是更好地理解二十年前的一篇里程碑论文《Natural proofs》，它让他浮想联翩。这篇论文来自复杂性实践研讨者 Alexander Razborov 和 Steven Rudich，其中注明：用于注明 P ≠ NP 的一种特定的「当然」策略几乎必定会失败，因为其成功的代价非常高（密码学的彻底崩溃），以至于研讨者认为这非常不能够实现。研讨者将 Razborov 和 Rudich 研讨结果解释成无法使用这种常用要领来注明 P ≠ NP。
对于复杂性实践领域的悬而未决的题目，有许多故障，这个「当然注明故障」只是其中之一。每一个故障都像一块拦路石，警告着人们：这条看似有希望的门路其实是条死路。这些故障合到一起，表明任何能办理 P 与 NP 题目的注明都必然截然不同于过去使用过的任何注明要领；也因此大多数研讨者都相信 P 与 NP 题目的解依然遥遥无期。但至少这些故障能告诉他们不用去某些地方找了。
Ilango 说：「有如此之多的故障，复杂性实践既是受诅咒的，也是被祝福的。」
当 Carmosino 遇到这个当然注明故障时，这个故障已经消失了近 20 年时间。但他认为它带给研讨者更多的是教训。他的这种感觉得到了证实。他与三位同事通过从元复杂性角度研讨当然注明而注明了这个令人惊讶的结果。有几项重大成果引发了人们对元复杂性的新兴趣，他们的注明便是其中之一，并在过去几年中催生了一系列进展。
但如果要了解从当然注明到元复杂性的研讨轨迹，我们必须回到 1970 年代研讨者们首次开始办理 P 与 NP 题目的时候。为什么注明题目很难的题目很难？
一条迂回曲折的道路
一开始，研讨者试图通过图灵用过的技术（图灵用来注明某些题目无法通过任何算法办理）的变体来注明 P ≠ NP，即注明某些 NP 题目无法通过任意能够的多项式算法办理。但他们很快在论文《Relativizations of the P=?NP Question》中发现了一个表明这些要领没有用的注明 —— 这是办理 P 与 NP 题目遇到的第一个主要故障。所以他们开始寻找另一种要领，他们很快在图灵的同时代人克劳德・香农的研讨成果中找到了一种。
克劳德・香农身穿西装的黑白照片。克劳德・香农在自己的硕士论文中发展出了一套基于电路的估计实践模型。
在密歇根州北部一个小镇长大的香农似乎不太能够成为信息时代的开创者。然而，他的成就体现了估计机科学这一新兴学科的跨学科性质 —— 电气工程和数理逻辑各半。香农在自己的硕士论文《A symbolic analysis of relay and switching circuits》中展示了可以如何使用机电开关组成的电路表示涉及布尔变量的逻辑表达式；布尔变量是指只能取两个值（比如真和假或 1 和 0）的量。
在逻辑表达式中，布尔变量通过逻辑门与（AND）、或（OR）、非（NOT）连接到一起。举例来说，只有当 A 和 B 皆为真时，基本表达式 A AND B 才为真，否则为假；而只要 A 和 B 中至少一个为真，A OR B 便为真。NOT 门甚至更简单：它会翻转变量的真值。有了足够多这些基本的构建模块，就能执行任意估计。
「当你看你的电脑时，究其根本，它到底在做什么呢？它在运行一个电路。」Ilango 说。
香农的研讨为实践研讨者提供了一种思考估计题目难度的新要领，即「电路复杂性（circuit complexity）」，即便这里提到的电路只是数学抽象。有一段时间，研讨者认为这种要领可以办理 P 与 NP 题目，但最终这条道路撞上了上述的当然注明故障。
房屋大小的 Harvard Mark I（哈佛一型）估计机的黑白照片。这张照片摄于 1944 年，这台 Harvard Mark I 估计机的构建模块是机电开关，正如香农在其论文中分析的那样。
这个电路复杂性框架需要重新思考图灵的估计模型中最基础的概念。在这里，研讨者考虑的不是估计题目和办理题目的算法，而是布尔函数和估计这些函数的电路。布尔函数以布尔变量（真或假，1 或 0）为输入，输出的也是真或假、1 或 0。与算法类似，电路描述的也是在任意输入下得到输出的过程。
「我的理解是，人们开始研讨电路复杂性，因为他们认为图灵机太复杂了。」MIT 复杂性实践研讨者 Ryan Williams 说，「我们一个门接一个门地研讨电路。」
我们知道有许多用于办理特定估计题目的算法，其中一些算法比其它算法更快；类似地，也有许多不同的电路可以估计给定的布尔函数，其中一些电路的门数量比其它门更少。研讨者将函数的电路复杂性定义成了估计该函数所需的最小电路的门总数。对于一个输入变量数量固定的函数而言，电路复杂度也是一个固定值 —— 某些函数的值高于其它函数。
具有同样真值表的不同布尔电路。
但在很多状况下，可以通过增加输入变量的数量来获得同一函数的更复杂版本，就像我们可以用更大的图来让哈密顿门路题目更加困难。研讨者在研讨算法运行时间时也考虑了同样的题目：随着输入变量增多，用于估计一个布尔函数的门的最小数量的增长是呈多项式模式还是指数级模式？研讨者将这两类函数分别称为「易于估计」和「难以估计」的函数。
一种易于估计的布尔函数类似于 P 类中的估计题目 —— 可以通过在多项式时间内运行完成的算法办理的题目。但也有些函数类似于困难的 NP 题目，其中研讨者使用已有的最好要领发现：估计更大的题目版本需要门的数量呈指数增长，然而其答案却可以被轻松验证。如果复杂性实践研讨者可以注明世上不消失估计出这样一个函数的更好要领，那就能说明 P ≠ NP。
这是 1980 年代大多数复杂性实践研讨者所奉行的策略。他们的胜算很大。香农在 1949 年通过论文《The synthesis of two-terminal switching circuits》注明，几乎每一个布尔真值表（就是一个固定大小的布尔函数的所有能够输入和输出的长列表）的电路复杂度实际上都是尽能够高的。他使用了一个简单得让人惊讶的论据：组合少量门的要领比组合许多门的要领少得多。
Aaronson 说：「小电路的能够性不够多。」
所以复杂性实践研讨者发现自己陷入了一个奇怪的境地。如果几乎每个真值表都有很高的电路复杂性，那么几乎每个布尔函数都必然难以估计。研讨者要做的就只有找到一个这样的函数，并确信其属于 NP 类。那会有多难？
加密兄弟
起初，进展迅速。1981 年，Sipser 与两位合作者写了一篇论文《Parity, circuits, and the polynomial-time hierarchy》，其中注明：如果一个特定的布尔函数使用的电路以一定的方式限制了门的排列方式，那么该布尔函数必定是难以估计的。
Sipser 说：「我们想的是先用这些受限的模型来注明一些东西，然后在获得的成果上继续探究限制越来越少的状况。」
Michael Sipser 身着蓝色纽扣衬衫。Michael Sipser 在 1981 年参与注明了一个基于受限电路的里程碑结果，但之后进展一直不佳。
1985 年，Razborov 迈出了下一大步。那时候他刚在莫斯科开始研讨生生涯，而这项成果完全是意外所得，那时候他其实正在研讨另一个数学分支的题目；结果表明办理 P 与 NP 题目是一个先决条件。
「我就是太幸运了，我当时不知道这个题目有多难。」Razborov 说，「否则我能够甚至都不会开始。」
在论文《Lower Bounds For The Monotone Complexity Of Some Boolean Functions》中，Razborov 分析了仅包含与门和或门的电路，并注明：无论如何排布这些门，使用这样的电路都难以估计一个特定的函数 —— 更重要的是，已知该函数就是 NP 齐备的。为了办理 P 与 NP 题目，研讨者要做的就只是将 Razborov 的技术扩展用于有非门的电路。
Razborov 说：「那时人们普遍有种感觉：只要再进一步，再获得一次发现，我们就能成功。」但那没有发生。Razborov 自己注明他的要领无法注明带有非门的状况，也没人能找到其它前进之路。多年以后，他开始思考这条路无法继续的原因。
Rudich 在美国思考着同样的题目。他和 Impagliazzo 是大学同学，后来一起读研讨生。他们的友情起点是他们都深深着迷于哥德尔和图灵的自我指涉注明以及他们对数学和估计机科学基础所造成的影响。
Impagliazzo 说：「我们开玩笑说，我们会得到一个写着『自我指涉』的按钮」。
身穿蓝色毛衣的 Alexander Razborov 和身穿蓝色衬衫的 Steven Rudich。Alexander Razborov（左）和 Steven Rudich 在 1994 年发现了当然注明的故障，这能解释为什么之前对 P ≠ NP 的注明尝试都失败了。
在读研讨生时，Rudich 和 Impagliazzo 都研讨过密码学的复杂性实践基础 —— 密码学也许能提供尝试注明 P ≠ NP 的最佳实践动机。加密学家隐藏秘密消息的要领是用「伪随机性」来隐藏它们 —— 以这种方式加密的消息在任何窃听者看来都像是随机排布的数字，但却可以被目标接收者解码。但我们能以何种方式确保潜在的窃听者会觉得破解太难而选择放弃呢？
这就是复杂性实践的用武之地。当今使用最广泛的加密要领都基于看似困难的 NP 题目 —— 要解密信息，攻击者需要一种尚未发现的快速算法来求解这个题目。为了确保这些要领是真正安全的，就需要注明 P ≠ NP。Sipser 说，如果没有对此的注明，你就只能「希望试图窥探你秘密之人不是比你优秀的数学家。」
尽管密码学本身确实也让人着迷，但似乎与最早将 Rudich 和 Impagliazzo 引入该领域的自我指涉论证相距甚远。但正当 Rudich 努力理解电路复杂性要领止步不前的原因时，他开始意识到这两个学科的距离其实并不远。研讨者为注明 P ≠ NP 所采用的策略具有一种自我推翻（self-defeating）的特性，这让人想起了哥德尔的著名命题：「本陈述是不可注明的」—— 而密码学可以帮助解释其原因。大概在同样时间，Razborov 在俄罗斯发现了类似的联系。这些都是当然注明故障的种子。
当然注明故障的核心关键是：区分高复杂度函数和低复杂度函数的任务类似于区分用于加密信息的真随机性和伪随机性的任务。我们希望注明高复杂度函数与低复杂度函数有本质区别，从而以此注明 P ≠ NP。但我们也希望无法区分伪随机性与真随机性，从而依然对密码学的安全性充满信心。也许我们无法两者兼得。
一个残酷的玩笑
1994 年，Razborov 和 Rudich 意识到他们有相似的见解，于是开始合作，将他们的研讨成果结合起来。他们首先观察到，之前所有利用电路复杂性注明 P≠NP 的尝试都采用了同样的一般性策略：确定一个 NP 齐备的布尔函数的特殊属性，然后注明易于估计的函数都不能够具有该属性。这能注明所选的 NP – 齐备函数确实难以估计，从而注明 P ≠ NP。
Sipser 和 Razborov 等研讨者都成功使用这一策略注明出了更有限的结果；在每一种状况下，研讨人员认定的特殊性质是大多数布尔函数都具有的性质。由于之前还没有描述这种属性被广泛具备的状况的术语，Razborov 和 Rudich 创造了 natural proof（当然注明）这一术语。如果「不当然」注明能够消失，那么它们必定非常反自觉，所以也担得起这个名字。
Razborov 和 Rudich 后来注明了他们的主要结果：对 P ≠ NP 的当然注明需要非常全面地理解易于估计的函数和难于估计的函数的差异之处；而这样的知识也可助力找寻用于识别易于估计的函数的快速算法，即便这些易于估计的函数表面上看能够很难。如果复杂性实践研讨者成功使用当然注明注明了 P ≠ NP，他们就能发现一种近乎万无一失的要领 —— 只需看一眼任意真值表，就能确定对应函数的电路复杂性是高是低。这是比他们想要注明的结果更强大更普适的结果。
Carmosino：「你无法控制，你会得到比自己想要的更多。」
这就好比你想检验某个特定陈述的事实，但每次尝试都会得到一个通用测谎仪的设计蓝图 —— 这也太好了吧，简直不像是真的。对于复杂性实践研讨者来说，当然注明力量惊人，但这也让其成功的能够性变得很小。但如果有这样一个注明成功了，那么由于电路复杂性和伪随机性之间的关联，这个意料之外的结果对密码学来说就是个坏消息了。
要理解这种关联，可以这样想象：在有许多输入变量的布尔函数的真值表的输出列中，使用 1 替换每一个「真」，使用 0 替换每一个「假」。
可用 0 和 1 表示布尔真值表的输出
如果这个布尔函数的电路复杂性很高，那么这个很长的输出列表原则上就无法与真正随机的 0 和 1 构成的字符串区分开 —— 比如通过不断掷硬币得到的字符串。但如果该函数的电路复杂性较低，这个字符串必定有一个简单的简明描述，即便其能够看起来很复杂。这使其非常类似密码学使用的伪随机字符串，其简明描述便是那表面的随机性之下隐藏的秘密消息。
伪随机字符串能够看似随机，但实际有一个简单的描述。
所以 Razborov 和 Rudich 的研讨结果表明：对 P ≠ NP 的任何当然注明都会得到一个快速算法，该算法能将包含隐藏信息的伪随机字符串与真随机字符串区分开。安全的加密将因此而不再能够 —— 这与研讨者试图通过注明 P ≠ NP 取得的目标刚好相反。
另一方面，如果安全的加密能够实现，那么当然注明就不是一种注明 P ≠ NP 的可行策略 ——P ≠ NP 是安全加密的先决条件。简而言之这就是当然注明故障。看起来，复杂性实践研讨者正在接收一个残酷的玩笑。
Kabanets 说：「如果你相信难度，那么你就应该相信难度是很难注明的。」
进入元宇宙
P≠NP 猜想的含义与注明该猜想的难度之间消失有趣的联系，但要确定这种联系却很难。一方面，当然注明故障只是阻碍一条注明 P ≠ NP 的途径。另一方面，它没有将注明 P ≠ NP 的难度与 P ≠ NP 自身关联起来，而是关联了安全加密要领的消失 —— 这是一个紧密相关但并不完全等价的题目。为了真正理解这种关联，研讨者必须熟悉元复杂性。
「人们有一种直觉：因为 P ≠ NP，所以难以注明 P ≠ NP。」Williams 说，「但为了理解这种直觉，你必须开始思考把注明 P ≠ NP 这样的任务作为估计题目。」
这正是 Kabanets 在研讨生阶段做的事。
Valentine Kabanets 戴帽子的户外照。Valentine Kabanets 在读研讨生时写了一篇颇具影响力的论文，其中论述了一个典型的元复杂性题目，他将其命名为「最小电路规模题目（MCSP）」。
「我当时想做一些学术性更强的事情。」Kabanets 回忆说，「我也很想看看这个世界。」他来到加拿大读研讨生，正是在这里他了解到了当然注明故障。Kabanets 和 Carmosino 一样被这一结果迷住了。他说：「这一联系看起来意义重大。」
2000 年，在他的研讨生阶段行将结束时，他发现当然注明故障经常出现在他与 Jin-Yi Cai（蔡进一）的对话中，蔡进一是一位复杂性实践研讨者，当时正在多伦多学术休假。他们不再将这个故障看作是一块拦路石，而是一份邀请 —— 一个探究「注明题目很难」这个任务到底有多难的机会。他们给出这一新视角的论文《Circuit minimization problem》将成为新生的元复杂性领域最富影响力的早期研讨成果之一。
Kabanets 和蔡进一的论文强调了 Razborov 和 Rudich 形式化描述的当然注明故障中隐含的一个估计题目：给定一个布尔函数的真值表，确定其电路复杂性是高还是低。他们称之为最小电路规模题目（MCSP）。
MCSP 是一个典型的元复杂性题目：这类估计题目关注的不是图论或其它外部主题，而是复杂性实践本身。实际上，它就像是 1980 年代那个题目的定量版本 —— 这个题目促使复杂性实践研讨者使用电路复杂性要领来办理 P 与 NP 题目；这个题目就是：哪些布尔函数难以估计，哪些又易于估计？
「如果我们能想出一种 MCSP 算法，那就会成为一种自动化复杂性实践研讨的要领。」Impagliazzo 说，「它至少能让我们深入了解可以如何更好地完成我们的工作。」
复杂性实践研讨者并不担心这种神奇的算法会让他们失业 —— 他们认为它根本就不消失，因为 Razborov 和 Rudich 的研讨表明这种用于分辨高与低复杂度真值表的算法会让安全加密变得不能够实现。这意味着 MCSP 很能够是一个困难的估计题目。但这个题目究竟有多难？它是 NP – 齐备的吗，就像哈密顿门路题目等研讨者们在 1960 年代苦苦探究的题目？
对于 NP 题目而言，「有多难？」通常容易回答，但 MCSP 似乎是一个奇怪的例外。Kabanets 说：「我们有一些很少的『漂浮不定的』题目，它们没有连接到 NP 齐备题目之岛，即便它们看起来很难。」
Kabanets 知道他和蔡进一并非最早思考被他们命名为 MCSP 的题目。苏联的数学家早在 1950 年代就研讨过一个非常相似的题目，那时候他们是想尝试理解不同估计题目的固有难度。莱昂尼德・列文在 1960 年代末发展后来的 NP – 齐备性实践时也曾与这个题目搏斗过，但他没能注明它是 NP 齐备的，而且他发表的开创性论文中也没有它。
之后 30 年里，这个题目都鲜有人关注，直到 Kabanets 和蔡进一注意到了其与当然注明故障之间的联系。Kabanets 当时并不指望靠自己办理这个题目 —— 他想做的是探索其如此之难的原因以注明：这个看似困难的关于估计难度的题目实际上很难。
牛津大学复杂性实践研讨者 Rahul Santhanam 说：「从某种意义上说，这是元 – 元复杂性（meta-meta-complexity）」。
但是，是这个题目一直都很难，还是说至少消失某种要领可以解释为什么研讨者没能成功注明 MCSP 是 NP 齐备的？Kabanets 发现确实消失一个原因：理解电路复杂性的困难就像是一个故障，阻碍着研讨者使用任何已知的策略来注明 MCSP 的 NP 齐备性，而 MCSP 这个题目本身就是关于理解电路复杂性的困难的。当然注明故障那扭曲的、自我推翻的逻辑似乎无法避免。
MCSP 也有能够不是 NP 齐备的，但这也似乎不太能够 —— 人们已经知道该题目某些更简单的变体是 NP 齐备的。
此维恩图展示了 MCSP 在 NP 类估计题目中的位置。
Impagliazzo 说：「我们不知道该把这个题目置于何处，使之能与我们研讨的其它题目直接联系起来。」
Kabanets 已经阐明了 MCSP 的奇怪行为，但他不知道如何才能更进一步。元复杂性研讨速度放缓了。16 年后，研讨者发现其与另一个基础题目之间消失惊人的联系，这时候元复杂性研讨才再次迎来繁荣。这个基础题目是：如果我们只关心得到大多数时候都正确的答案，那么办理题目有多难？
对于日常题目来说，大多数状况下有效的答案往往就已经足够好了。举个例子，规划交通时，我们往往是根据典型的交通模式，而非最糟糕的状况。
大多数复杂性实践研讨者都难以满足：如果他们能找到一种能为每个能够输入得到正确答案的快速算法，他们才会满足地宣布这个题目是容易的。这种标准要领是根据研讨者所称的「最坏状况」复杂度来对题目进行分类的。但还消失一种「一般状况」复杂性实践，即如果消失一种能在大多数输入下都能得到正确答案的快速算法，则该题目就可被视为是容易的。
这种区别对密码学研讨者来说很重要。请想象有这样一个估计题目，其几乎所有输入都容易求解，只有少数状况例外 —— 即使最好的算法也无能为力。最坏状况复杂性实践把这视为一个困难题目，但对密码学而言这没有任何用处。如果你的消息中仅有一部分难以解码，哪还有什么意义呢？
最早开始严格地研讨一般状况复杂性实践的正是列文，那是在他完成了自己在 NP 齐备性方面的开创性成果的十年之后。
列文在 1978 年移民到了美国，到 1980 年代中叶，他的注意力转向了一般状况复杂性。他开始与其他人合作进一步推进这一实践，其中包括当时正在读研讨生的 Impagliazzo。但在他们取得进展的同时，Impagliazzo 发现研讨者们常常自说自话。他希望每个人都达成一些共识，而列文的论文又是出了名地简洁 —— 开创一般状况复杂性领域的论文《Average Case Complete Problems》不到两页长。
Impagliazzo 说：「我打算把莱昂尼德的研讨成果翻译成更通俗易懂的专业术语。」他决定先写一些简短的带着打趣玩笑的综述，在深入数学内容前描绘一番该领域的概况。「这部分内容变成了整篇论文的代表，也是大家唯一记得的部分。」
这篇论文是《A personal view of average-case complexity》，在 1995 年一发表出来便成了经典。针对按照不同估计难度和不同加密能力划分的五个世界，Impagliazzo 为它们起了些古怪离奇的名字。我们生活在其中一个世界，但我们不知道是哪一个。
身穿红色毛衣的 Russell Impagliazzo 与身穿黄色衬衫坐在室外的莱昂尼德・列文。莱昂尼德・列文（右）于 1980 年代中期开始研讨一般状况复杂性。Russell Impagliazzo 之后写了一篇关于我们生活的五个估计世界的标志性论文，让这一学科更为人所知。
自 Impagliazzo 的论文问世以来，研讨者就一直梦想着消除其中的微型多元宇宙部分 —— 通过注明某些世界根本不能够消失来缩小能够性范围。有两个世界是尤其诱人的目标：在这两个世界中，即便 P ≠ NP，加密也是不能够的。
其中一个世界被称为 Heuristica（启发之地）；在这个世界中，所有 NP – 齐备的题目都在大多数输入上容易求解，但快速算法偶尔会出错，所以在最坏状况复杂性实践的标准下，这些题目会被认为是困难的。这是一个加密不能够实现的世界，因为几乎每个代码都容易被破解。另一个世界则名为 Pessiland；这也是一个加密不能够实现的世界，但原因不同：每个题目在一般状况复杂性标准下都是困难的，但对信息加密之后，即便是预期的接收者也将无法辨别。
事实注明，这两个世界与元复杂性题目紧密相关 —— 尤其是 Heuristica，其关乎着 MCSP 是否 NP 齐备这个长时间都未能得到办理的题目。这个让 Kabanets 着迷并阻碍列文如此之久的题目不仅仅是一个满足好奇心的题目：它还关乎一整个世界。
为了排除 Heuristica 的能够性，研讨者必须弥合最坏状况和一般状况复杂性之间的区别 —— 也就是说，他们必须注明：假设消失能在大多数输入上正确办理一个 NP 齐备题目的算法，那么该算法实际上能在所有状况下办理该题目。这种关联被称为「最坏状况到一般状况的约简」。人们已经知道某些特定题目消失这种现象，但它们都不是 NP 齐备的，因此这些结果无法说明更一般的状况。在基于 P ≠ NP 这一单一假设实现安全加密的梦想之路上，如果能消除 Heuristica，密码学家就算取得了一半的成功。
2003 年，两位复杂性实践研讨者在论文《On worst-case to average-case reductions for NP problems》中表明：用于为已知 NP 齐备题目注明最坏状况到一般状况的约简的现有要领都会有极不寻常的后果，这表明这样的注明也许不能够消失。
研讨者们就不得不去找寻另一种要领，而现在他们认为 MCSP 也许正是他们所需的题目。但他们要到十多年后才明白这一点。Marco Carmosino 对当然注明故障的执着和痴迷让他最先看到了这两者之间的联系。
三、机遇
Carmosino 最早与元复杂性研讨相遇是在其研讨生阶段，那时候他读到了 Kabanets 与另外四位研讨者在 2013 年发表的一篇论文《Mining Circuit Lower Bound Proofs for Meta-Algorithms》，其中进一步发展了 Kabanets 在十多年前开创的用于当然注明故障的要领。这让他更加坚信，还能从 Razborov 和 Rudich 的经典论文中学到更多东西。
「那时候我对那篇论文着迷了。」Carmosino 说，「到现在一切都没变。」
这种痴迷最终带来了收获；那是在加州大学伯克利分校的一个为期一个学期的研习班上，他来到这里并把大部分时间都用于与 Impagliazzo、Kabanets 和 Antonina Kolokolova 讨论。Antonina Kolokolova 是来自纽芬兰纪念大学的一位复杂性实践研讨者，她是 Kabanets 2013 年那篇论文的合作者之一。Carmosino 曾与他们三人合作过一次，那次成功合作给了他信心，让他不断向他们提出有关这一主题的最让自己着迷的题目。
Kabanets 回忆说：「他在骚扰人，但方式是好的。」
一开始的时候，Carmosino 有一些新想法，可用于注明出现在 Razborov 和 Rudich 的关于当然注明故障的论文中的那个版本的 MCSP 的 NP 齐备性。但这些想法没能取得成功。相反，Impagliazzo 的一句随口之言让那四位研讨者意识到，当然注明故障可以衍生出比任何人以为的都更强大的算法 —— 这个路障之上篆刻着一副隐秘地图。
Antonina Kolokolova 身穿一件蓝色毛衣坐在一张桌子前。2016 年，Antonina Kolokolova 与 Carmosino、Impagliazzo 和 Kabanets 共同注明 MCSP 与学习之间消失惊人的联系，这让人们再次关注起元复杂性。
在 2016 年的论文《Learning algorithms from natural proofs》中，这四位研讨者注明：一种特定类别的一般状况 MCSP 算法可用于构建一种最坏状况算法 —— 该算法可用于识别看似随机的数字串中隐藏的模式。该任务被估计机科学家称为「学习（learning）」。这个结果很惊人，因为直觉上看，学习似乎比 MCSP 算法执行的二元分类任务更难 —— 高复杂度或低复杂度。而且出人意料的是，它将一个任务的最坏状况复杂性与另一个任务的一般状况复杂性联系到了一起。
Impagliazzo 说：「这种联系的消失并不是显而易见的。」
对于一般布尔电路来说，MCSP 的快速算法仅仅消失于假设中：除非能注明 MCSP 是一个容易的估计题目，否则这个快速算法不能够消失，尽管所有的证据都指向相反的结论，这意味着这四位研讨者的论文所暗示的学习算法同样仅消失于假设之中。
但对于 MCSP 的一些更简单的版本 —— 在对电路有特定限制时，区分高复杂度真值表和低复杂度真值表 —— 快速算法早已为人所知多年。Carmosino、Impagliazzo、Kabanets 和 Kolokolova 的论文表明，这些算法可以转换为学习算法，这些算法同样受到限制，但仍然比研讨者以前在如此严格的实践层面上理解的任何算法都要强大。
Ilango 说：「不知为何，它们的自我指涉方面让你能做一些似乎无法对更标准的题目做的事情。」
这一结果吸引了研讨其它课题的复杂性实践研讨者的关注。对于将在未来几年发现的元复杂性和一般状况复杂性之间的进一步联系，这一结果也算是一个预演。
最重要的是，这一结果注明：研讨者可以通过提出简单题目来办理那些初看似乎只会阻碍他们前进的故障。
「这种两面性是过去至少三四十年复杂性研讨的一大主题。」Impagliazzo 说，「故障往往也是机遇。」
关于部分的成果
Carmosino 及同事们发表了那篇论文之后几年，研讨进展加快了。
复杂性研讨百年史
「新成果正在出现。」Kolokolova 说，「现在有很多非常非常聪明的年轻研讨者。」
Ilango 就是这样一位年轻研讨者 —— 在读研讨生的前三年，他攻克了注明 MCSP NP 齐备性这一悬而未决的艰巨难题，他使用了一种双管齐下策略：一方面是注明 MCSP 的更简单版本的 NP 齐备性，正如电路复杂性研讨者在 1980 年代攻坚 P 与 NP 题目那样，见论文《The Minimum Formula Size Problem is (ETH) Hard》；另一方面是注明更复杂版本的 NP 齐备性，这些题目直觉上看来更难，因此更容易注明它们很难，见论文《Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC^0 [p]》。
Ilango 将自己对元复杂性的研讨兴趣归功于 Eric Allender，他是罗格斯大学一位复杂性实践研讨者，也是少数几位在 2000 年代和 2010 年代早期仍继续研讨元复杂性的研讨者之一。Ilango 说：「他的热情很有感染力。」
另一位受到 Allender 激励的年轻研讨者是平原秀一（Shuichi Hirahara），他现在是东京国立情报学研讨所的一位教授。2018 年平原还是一位研讨生时，他就揭示出了 Carmosino 与其合作者发现的元复杂性和一般状况复杂性之间的关系的真实程度。那四位研讨者已经发现一个题目（MCSP）的一般状况复杂性与另一个题目（布尔学习）的最坏状况复杂性之间消失联系。平原进一步发展了他们的技术，在论文《Non-Black-Box Worst-Case to Average-Case Reductions within NP》中推导了 MCSP 从最坏状况到一般状况的约简。他的研讨结果表明一种假设消失的一般状况 MCSP 算法（就像 Carmosino 及其同事考虑过的那个）实际上是足够强大的 —— 足以毫无差错地求解一种稍有不同的 MCSP。
平原的研讨结果激动人心，因为很多研讨者猜测 MCSP 是 NP 齐备的，这不同于其它所有已经知道从最坏状况到一般状况约简的题目。如果他们能扩展平原的结果，使之覆盖所有一般状况算法，然后注明 MCSP 是 NP 齐备的，那就能注明我们的世界不是 Heuristica。
Santhanam 说：「那会是一个震天撼地的结果。」
注明 MCSP 是 NP 齐备的似乎是一项艰巨的任务 —— 毕竟，这个题目已经悬而未决了 50 多年。但在平原 2020 年的突破性研讨成果《NP-Hardness of Learning Programs and Partial MCSP》之后，研讨者们现在离注明它要近得多了，超出了几年前任何人的预期。
平原注明了该题目的一个名为部分 MCSP（partial MCSP）的变体版本的 NP 齐备性；在部分 MCSP 中，每个真值表中都有一部分条目被忽略。他的注明基于 Ilango 开发的要领，其表明部分 MCSP 等价于一个看似无关的题目，该题目涉及一种名为秘密共享（secret sharing）的加密技术。这种要领是把已加密的消息分给许多人，使得只有当一定比例的人合作起来才能将其解码。
对密码学的任何真实应用而言，你都希望提前知道这个比例是多少，但借助于额外的密码学技巧，你可以构建一个令人沮丧的场景，其中光是知道需要多少人合作就已经非常困难。平原找到了一种要领来注明这个假定的密码学题目是 NP – 齐备的，然后他又注明这个注明也意味着部分 MCSP 的 NP 齐备性。
身穿蓝色衬衫的 Rahul Ilango 与身穿蓝色西装外套的平原秀一。Rahul Ilango（左）与平原秀一最近开发一种新的加密技术来注明 MCSP 的一种变体是 NP 齐备的。
这一结果给元复杂性研讨者带来的激励甚至超过平原更早的研讨成果，其他研讨者也注意到了它 —— 复杂性实践研讨者和博客作者 Lance Fortnow 将其称为当年的年度成果。这是因为办理估计题目的这种「部分函数」版本一直都是其它 NP 齐备性注明的一个关键中间步骤。
「这是一项了不起的成果。」Williams 说，「所有人都曾以为这些部分题目的难度与完整题目大致一样。」
此维恩图展示了分类 MCSP 变体版本的复杂度的最近进展。
在注明完整版的 MCSP 的 NP 齐备性方面，故障依然消失。但这些故障表现出的样子说明办理它们并不需要一套全新的工具 —— 关键能够就只是找到一种正确组合已知技术的方式。如果能成功注明，就能分类一个自复杂性实践诞生以来就一直未被成功分类的题目，而这样一直未被分类的题目可不多。列文在一份电子邮件中写道：「这会让我感到谦卑，因为这说明我很愚蠢，竟没能看到它。」
缺失的拼图
MCSP 甚至不是唯一一个实现了重大突破的元复杂性题目。2020 年时，在论文《On One-way Functions and Kolmogorov Complexity》中，康奈尔大学科技校区的密码学家 Rafael Pass 与其研讨生刘研绎（Yanyi Liu）发现一个不同的元复杂性题目与一种基础加密协议之间消失某种联系 —— 这个加密协议定义了 Heuristica 和 Pessiland 的疆界，而 Pessiland 是 Impagliazzo 定义的世界中最糟糕的那个。（在 Pessiland 中，NP 齐备题目在一般状况下是困难的，但加密也不能够实现。）这使得他们研讨的题目成为了攻击 Pessiland 的主要候选题目，而他们更近期的一项研讨成果《On one-way functions from NP-complete problems》表明这也能用于证否 Heuristica。
「这幅拼图缺失了不同的碎片。」Pass 说，「在我看来，这些领域的联系是如此紧密，实在太神奇了。」
平原警告说，对于想要证否 Impagliazzo 在 30 年前创造的某些世界的研讨者而言，挑战依然消失。他说：「我想说的是，Heuristica 和 Pessiland 将会在某个时刻被排除掉，但我不知道我们离那一刻还有多远。」
很多研讨者预计最大的困难将是弥合两种不同的一般状况复杂性模型之间看似无关紧要的差距。密码学研讨者通常研讨的是在两个方向上都会出错的一般状况算法 —— 偶尔会将随机字符串错误地标记成伪随机或把伪随机字符串错误标记成真随机。而平原从最坏状况到一般状况的约简则适用于仅会犯第一类错误的一般状况算法。类似这样的微妙差异在复杂性实践领域却是天差地别。尽管有这个以及其它许多阻碍，但 Allender 还是不禁发出了谨慎乐观的声音。
「我尽量让自己不要过于乐观，因为过去的研讨历史表明没什么是行得通的。」他说，「但我们正在见证很多真正激动人心的发展 —— 克服那些似乎是故障的要领。」
在解答 P 与 NP 题目（或者仅仅是为了理解它）的过程中，如果说研讨者从自己的苦苦求索中获得了什么教训，那就是复杂性实践本身就很复杂。但这种挑战性正是这条求索之路的意义所在。
「这个题目如此之难实际上算是件好事。」Carmosino 说，「我永远不会感到无聊。」
原文链接：https://www.quantamagazine.org/complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/