复杂性理论50年的知识极限之旅| 广达杂志

2007 年秋季学期的第一周，马可·卡莫西诺 (Marco Carmosino) 硬着头皮去参加马萨诸塞大学阿默斯特分校所有计算机科学专业必修的数学课。 卡莫西诺是一名大二学生，他正在考虑从大学退学去设计电子游戏。 然后教授提出了一个改变他一生的简单问题：你怎么知道数学确实有效？

“这让我坐起来并集中注意力，”回忆道 卡莫西诺，现在是 IBM 的理论计算机科学家。 他报名参加了一个关于库尔特·哥德尔工作的可选研讨会，哥德尔令人眼花缭乱的自我参照论证首先暴露了数学推理的局限性，并为未来所有关于计算基本极限的工作奠定了基础。 有很多东西需要接受。

“我百分百不明白，”卡莫西诺说。 “但我知道我想这么做。”

如今，即使经验丰富的研究人员在面对理论计算机科学中的核心开放问题（即 P 与 NP 问题）时也会发现理解不足。 从本质上讲，这个问题问的是，许多长期以来被认为极其困难的计算问题实际上是否可以轻松解决（通过我们尚未发现的秘密捷径），或者是否像大多数研究人员怀疑的那样，它们确实很困难。 关键在于可知事物的本质。

尽管研究人员在计算复杂性理论领域（研究不同问题的内在难度）付出了数十年的努力，但 P 与 NP 问题的解决方案仍然难以捉摸。 甚至还不清楚未来的证据应该从哪里开始。

“没有路线图，”说 迈克尔·西普瑟是麻省理工学院的一位资深复杂性理论家，他在 1980 世纪 XNUMX 年代花了数年时间来解决这个问题。 “这就像你走进了荒野。”

看来证明计算问题难以解决本身就是一项艰巨的任务。 但为什么这么难呢？ 这到底有多难？ 卡莫西诺和元复杂性子领域的其他研究人员将此类问题重新表述为计算问题，通过将复杂性理论的视角重新转向自身来推动该领域向前发展。

“你可能会想，‘好吧，这很酷。 也许复杂性理论家已经疯了，”说 拉胡尔·伊兰戈是麻省理工学院的一名研究生，最近在该领域取得了一些最令人兴奋的成果。

通过研究这些内向问题，研究人员了解到，证明计算难度的难度与乍一看似乎无关的基本问题密切相关。 在看似随机的数据中发现隐藏的模式有多难？ 如果确实存在真正困难的问题，那么它们有多困难？

“很明显，元复杂性接近事物的核心，”说 斯科特·阿伦森，德克萨斯大学奥斯汀分校的复杂性理论家。

这是一个漫长而曲折的故事，引导研究人员从 P 与 NP 问题转向元复杂性。 这并不是一次轻松的旅程——道路上布满了错误的转弯和路障，而且一次又一次地循环。 然而对于元复杂性研究人员来说，进入未知领域的旅程本身就是奖励。 开始问看似简单的问题，说 瓦伦丁卡巴内茨加拿大西蒙弗雷泽大学的复杂性理论家，“你不知道自己要去哪里。”

已知未知

P 与 NP 问题的名字暗淡无光，因为复杂性理论学家习惯将计算问题分类为广泛的“复杂度等级” 带有暗示纳斯达克股票代码的标签。 计算问题原则上可以通过算法（精确指定的指令列表）来解决。 但并非所有算法都同样有用，算法之间的差异暗示了不同类别问题之间的根本差异。 复杂性理论家面临的挑战是将这些提示转化为关于复杂性类别之间关系的严格定理。

这些关系反映了有关计算的永恒真理，远远超出了任何特定技术。 “这就像发现宇宙法则一样，”卡巴内茨说。

“P”和“NP”是最著名的两个成员 不断成长的动物园 数百个复杂性类别。 粗略地说，P 是一类可以轻松解决的问题，就像按字母顺序排列列表一样。 NP 是一类具有易于检查解决方案的问题，例如数独谜题。 由于所有容易解决的问题也很容易检查，因此 P 中的问题也属于 NP 中。 但有些 NP 问题似乎很难解决——如果不先尝试许多可能性，你就无法立即凭直觉找到数独谜题的解决方案。 难道这种表面上的困难只是一种幻觉——有一个简单的技巧可以解决每个容易检查的问题吗？

如果是这样，则 P = NP：这两个类是等价的。 如果是这样的话，一定有某种算法可以让解决巨大的数独难题、优化全球航运路线、破解最先进的加密以及自动化数学定理证明变得微不足道。 如果 P ≠ NP，那么许多原则上可以解决的计算问题实际上将永远超出我们的掌握。

早在 P 与 NP 问题第一次被阐明之前——事实上，早在现代计算机科学开始之前，研究人员就担心形式数学推理的局限性。 1921 年，数学家戴维·希尔伯特 (David Hilbert) 正在努力解决同样的问题，这个问题在近一个世纪后引起了卡莫西诺的注意，他提出了一项研究计划，以绝对确定性为数学奠定基础。 他希望从一些简单的假设（称为公理）开始，推导出满足三个关键标准的统一数学理论。

希尔伯特的第一个条件，一致性，是数学不存在矛盾的基本要求：如果可以从相同的公理出发证明两个矛盾的陈述，则整个理论将无法挽救。 但一个理论可能没有矛盾，但其范围仍然有限。 这就是希尔伯特第二个条件完整性的动机：要求所有数学陈述要么可证明为真，要么可证明为假。 他的第三个标准是可判定性，要求有一个明确的机械程序来确定任何数学陈述是真是假。 希尔伯特在 1930 年的一次会议上发表讲话时宣称：“我们的口号是‘我们必须知道，我们将会知道。’”

仅仅一年后，哥德尔就给希尔伯特的梦想带来了第一次打击。 他 证明 像“这个陈述是无法证明的”这样的自欺欺人的陈述可以从任何适当的公理集合中导出。 如果这样的陈述确实无法证明，那么这个理论就是不完整的，但如果它可以证明，那么这个理论就是不一致的——这是一个更糟糕的结果。 在同一篇论文中，哥德尔还证明，没有任何数学理论能够证明其自身的一致性。

研究人员仍然抱有希望，认为未来的数学理论虽然不一定完整，但仍可能被证明是可判定的。 也许他们可以开发出程序来识别所有可证明的陈述，同时避开像哥德尔这样令人烦恼的命题。 问题是没有人知道如何推理这些假设的程序。

1936年，23岁的研究生艾伦·图灵用当时还不熟悉的计算语言重新表述了希尔伯特的可判定性条件，并给了它致命的一击。 图灵制定了一个数学模型——现在被称为 图灵机 ——这可以代表所有可能的算法，并表明如果希尔伯特过程存在，它将适合这个模型。 然后他使用像哥德尔这样的自我指涉方法来 证明 无法判定的语句的存在——或者等效地，没有算法可以解决的不可计算的问题。

希尔伯特的计划已成为废墟：可证明的内容和可计算的内容将永远受到根本限制。 但随着计算机从理论抽象发展到真实机器，研究人员意识到图灵对可解决问题和不可解决问题的简单区分留下了许多悬而未决的问题。

到 1960 世纪 XNUMX 年代，计算机科学家已经开发出快速算法来解决某些问题，而对于其他问题，唯一已知的算法却慢得令人难以忍受。 如果问题不只是问题是否可以解决，而是解决起来有多困难怎么办？

“丰富的理论出现了，但我们不再知道答案，”卡莫西诺说。

分歧路径

为了说明有关硬度的问题是多么令人困惑，让我们考虑一对涉及图形的密切相关的问题。 这些是由称为节点的点组成的网络，通过称为边的线连接。 计算机科学家用它们来模拟一切 量子计算 到 流量.

假设给你一张图，并要求你找到一种称为哈密顿路径的东西——一条只经过每个节点一次的路线。 这个问题原则上显然是可以解决的：可能的路径数量是有限的，所以如果其他方法都失败了，你可以只检查每一条。 如果只有几个节点，那很好，但对于稍微大一点的图，可能性的数量会急剧失控，很快就会使这个简单的算法变得毫无用处。

有更复杂的哈密顿路径算法可以提供更好的战斗，但算法解决问题所需的时间总是随着图的大小呈指数增长。 研究人员发现，在即使是最好的算法也无法“在任何合理的时间内”找到路径之前，图不必非常大。 罗素因帕利亚佐，加州大学圣地亚哥分校的复杂性理论家。 “我所说的‘合理的时间’是指‘宇宙终结之前’。”

哈密​​顿路径问题还有另一个有趣的特性。 如果有人声称在特定图上找到了哈密顿路径，即使图非常大，您也可以快速检查解决方案是否有效。 您需要做的就是沿着路径并一一勾选节点，并检查以确保没有在任何节点上勾选两次。 如果最后没有丢失节点，则该路径是哈密顿路径。

运行此解决方案检查算法所需的时间与图的大小成正比。 这将其归入更广泛的多项式算法类别，其运行时间随着图大小的多项式函数而增加。 与指数增长相比，多项式增长是温和的，因此多项式算法即使在大型图上也仍然可行。 “它的效率显着提高，”卡莫西诺说。

哈密​​顿路径问题具有明显的不对称性：您可以使用快速多项式算法验证正确的解决方案，但要找到解决方案，您需要缓慢的指数算法。 这种不对称性似乎并不令人惊讶——认识一件艺术杰作比创造一件艺术杰作更容易，检查数学证明比证明一个新定理更容易——但并非所有计算问题都具有这种不对称特征。 事实上，与寻找哈密顿路径非常相似的问题的行为却截然不同。

假设再次给你一张图，但现在要求你找到一条与每条边恰好交叉一次的“欧拉路径”。 同样，有一个多项式算法来检查可能的解决方案，但这次还有一个多项式算法来解决问题。 这里没有不对称。 在复杂性理论中，某些路径似乎比其他路径更容易找到。

哈密​​顿路径问题和欧拉路径问题都属于复杂度类别 NP，定义为包括其解决方案可以通过多项式算法检查的所有问题。 欧拉路径问题也属于 P 类，因为多项式算法可以解决它，但从表面上看，哈密顿路径问题并非如此。 为什么这两个表面上如此相似的图形问题却有如此巨大的差异？ 这就是 P 与 NP 问题的本质。

普遍困难

起初，复杂性类别似乎是对相似但不直接相关的问题进行排序的方便类别——没有人怀疑寻找哈密顿路径与其他困难计算问题有任何关系。

然后在 1971 年，在被美国拒绝终身教职后搬到多伦多大学的一年内，这位复杂性理论家 史蒂芬·库克 发表 非凡的结果。 他发现了一个特定的 NP 问题具有一个奇怪的特征：如果有一个多项式算法可以解决该问题，那么它也可以解决 NP 中的所有其他问题。 库克的“普遍”问题似乎是一个单独的柱子，支撑着一类看似困难的问题，将它们与下面的简单问题分开。 解决了这个问题，NP 的其余部分就会崩溃。

库克怀疑没有快速算法可以解决他的普遍问题，他在论文中也说了同样的话，并补充道，“我觉得值得花费相当大的努力来证明这个猜想。” “相当大的努力”将被证明是轻描淡写的。

大约在同一时间，苏联的一名研究生名叫 列昂尼德·莱文 证明了一个 相似的结果，除了他发现了几个不同的普遍问题。 此外，美国复杂性理论家 理查德·卡普 证明 库克（和莱文，尽管卡普和库克直到几年后才知道莱文的工作）所确定的普遍性属性本身几乎是普遍的。 几乎所有没有已知多项式算法的 NP 问题（也就是说，几乎每个看似困难但易于检查的问题）都具有相同的属性，即 NP 完整性。

这意味着所有 NP 完全问题——哈密顿路径问题、数独和 数千 别人的 ——在精确意义上是等价的。 “你有所有这些不同的自然任务，但它们都神奇地变成了同一个任务，”伊兰戈说。 “我们仍然不知道同样的任务是否可能。”

解决任何 NP 完全问题的难度就足以解决 P 与 NP 问题。 如果 P ≠ NP，则简单问题和困难问题之间的区别由数千个同样强的列支撑。 如果P=NP，整个大厦就摇摇欲坠，只等一块倒塌。

库克、莱文和卡普统一了许多看似不相关的问题。 现在复杂性理论家所要做的就是解决一个问题：P = NP 吗？

五十年后，这个问题仍然没有答案。 卡巴内茨将关于计算局限性的推理比作在没有任何全局意识的情况下测量广阔的领土。 拥有无限计算能力的生物可以从山顶俯瞰整个景观，但凡人无法指望这种优势。 “我们这些在山脚下的人可以尝试跳上跳下以获得更好的视野，”他说。

假设 P = NP。 为了证明这一点，研究人员需要找到一种快速算法来解决 NP 完全问题，该问题可能隐藏在广阔景观的某个不起眼的角落里。 不能保证他们会很快找到它：复杂性理论家偶尔会发现 发现 经过数十年的工作，才找到了解决看似困难（尽管不是 NP 完全）问题的巧妙算法。

现在假设 P ≠ NP。 证明这一点似乎更加困难。 复杂性理论家必须证明，不可能存在快速算法，从而有效地预测和阻碍所有未来研究人员的最佳努力。

不知道从哪里开始是问题的一部分。 但这并不是研究人员没有尝试过。 几十年来，他们从多个角度解决了这个问题，但发现道路处处受阻。 “这是理论计算机科学中最明显的事实之一，”卡莫西诺说。 “当你遇到一种如此持久的现象时，你需要一些解释。”

在卡莫西诺大学的最后一年，他的好奇心引导他从哥德尔转向复杂性理论的研究生课程。 他惊讶地发现自己花在家庭作业上的时间比花在他所热衷的项目上的时间还要多，这个项目是一个可以学习童话故事叙事结构并生成新故事的计算机程序。

“我想，‘哇，我需要认真对待这件事，’”卡莫西诺回忆道。 不久之后，他对这个学科如此着迷，以至于他的导师温和地建议他重新考虑他的毕业后计划。

“他说，‘你知道，如果你想继续做这个，如果你想继续研究理论计算机科学和复杂性理论，你可以：这就是研究生院，’”卡莫西诺说。 获得硕士学位后，他于 2012 年搬到圣地亚哥，在 Impagliazo 的指导下攻读博士学位。

起初，卡莫西诺的主要目标是更好地了解 地标纸 二十年前，这激发了他的想象力。 那篇论文，由复杂性理论家撰写 亚历山大·拉兹博罗夫 和 史蒂文·鲁迪奇，已经表明证明 P ≠ NP 的某种“自然”策略几乎肯定会失败，因为成功将付出高昂的代价 - 密码学的彻底崩溃 - 研究人员认为这是非常不可能的。 研究人员将 Razborov 和 Rudich 的结果解释为这种证明 P ≠ NP 的流行方法的障碍。

这种“自然证明障碍”只是解决复杂性理论中开放问题的众多已知障碍之一。 每一个都像一个路障，警告看似有希望的道路实际上是一条死胡同。 总之，这些障碍表明，任何解决 P 与 NP 问题的证明都必须与过去使用的任何证明完全不同； 这就是为什么大多数研究人员认为解决方案还很遥远。 但至少障碍告诉他们哪里不该看。

“复杂性理论既受到诅咒，又受到如此多的祝福，”伊兰戈说。

当Carmosino遇到自然证明障碍时，它已经快20岁了。 但他怀疑这对研究人员来说有更多的教训。 当他和三位同事从元复杂性的角度检查自然证明障碍，证明了一个令人惊讶的结果时，这种感觉有一天会得到证实。 他们的证明是引发人们对元复杂性新兴趣的几个主要结果之一，从而在过去几年中取得了一系列进展。

但为了追踪从自然证明障碍到元复杂性的线索，我们必须跳回到 1970 世纪 XNUMX 年代研究人员第一次开始解决 P 与 NP 问题时的情况。 是什么让证明问题变得如此困难？

迂回之路

起初，研究人员试图证明 P ≠ NP——也就是说，证明某些 NP 问题无法通过任何可能的多项式算法解决——使用图灵用来证明某些问题无法通过任何算法解决的技术的变体。 但他们很快 发现 证明这些方法行不通——这是解决 P 与 NP 问题的第一个主要障碍。 所以他们开始寻找另一种方法，很快他们就在图灵同时代人的工作中找到了一种方法 克劳德香农.

香农在密歇根州北部的一个小镇长大，他似乎不太可能引领信息时代。 然而，他体现了计算机科学新兴学科的跨学科性质，在电气工程和数理逻辑方面同样感到自在。 在他的 硕士论文香农展示了由机电开关组成的电路如何表示涉及布尔变量的逻辑表达式——只能取两个值的量（例如 true 或 false，或 1 和 0）。

在这些表达式中，布尔变量通过“逻辑门”AND、OR 和 NOT 连接在一起。 例如，当 A 和 B 都为真时，基本表达式 A AND B 为真，否则为假； 另一方面，如果两个变量中至少有一个为真，则 A OR B 为真。 NOT 门甚至更简单：它反转单个变量的值。 有了足够的这些基本构建块，您就可以执行任何计算。

“当你看着你的电脑时，归根结底，它在做什么？ 它正在运行一个电路，”伊兰戈说。

香农的工作为理论家提出了一种思考计算问题难度的新方法，称为“电路复杂性”，即使所讨论的电路只是数学抽象。 有一段时间，研究人员认为这种方法可能是解决 P 与 NP 问题的方法，但最终该线索遇到了自然证明的障碍。

电路复杂性框架需要重新思考图灵计算模型中最基本的概念。 在这里，研究人员考虑的不是计算问题和解决它们的算法，而是布尔函数和计算它们的电路。 布尔函数接受布尔变量（true 和 false、1 和 0），并输出 true 或 false、1 或 0。与算法一样，电路描述了在给定任何输入的情况下生成输出的过程。

“我的理解是，人们开始研究电路复杂性，因为他们认为图灵机太复杂了，”说 瑞安·威廉姆斯（Ryan Williams），麻省理工学院的复杂性理论家。 “我们可以逐门研究电路。”

正如可以有许多算法来解决任何给定的计算问题，有些算法比其他算法更快一样，许多不同的电路可以计算任何给定的布尔函数，其中一些电路比其他电路具有更少的门。 研究人员将函数的电路复杂性定义为计算该函数的最小电路中的门总数。 对于具有固定数量输入变量的函数，电路复杂度也是一个固定数字——某些函数比其他函数更高。

但在许多情况下，您可以通过增加输入变量的数量来考虑同一函数的更复杂版本，就像您可以通过考虑更大的图来使哈密顿路径问题变得更加困难一样。 然后，研究人员考虑他们在研究算法运行时间时提出的同一问题：计算布尔函数所需的最小门数是否随着输入变量数量的增加而呈多项式或指数增长？ 研究人员分别将这两类函数称为“易于计算”和“难以计算”。

易于计算的布尔函数类似于 P 类中的计算问题——可以通过在多项式时间内运行的算法来解决。 但也有一些类似于硬 NP 问题的函数，研究人员发现，计算逐渐增大的版本的最佳方法需要指数级增加的门数量，但答案可以轻松检查。 如果复杂性理论家能够证明确实没有更好的方法来计算这样的函数，那就意味着 P ≠ NP。

这是 1980 世纪 XNUMX 年代大多数复杂性理论家所追求的策略。 胜算对他们有利。 香农有 证明 1949 年，几乎每个布尔真值表（只是固定大小的布尔函数的所有可能输入和输出的一长串列表）都具有实际上尽可能高的电路复杂性。 他使用了一个极其简单的论点：组合少量门的方法比组合许多门的方法少得多。

“没有足够的小电路可供使用，”阿伦森说。

因此，复杂性理论家发现自己处于一个奇怪的境地。 如果几乎每个真值表都具有很高的电路复杂性，那么几乎每个布尔函数都必须难以计算。 研究人员只需确定一个这样的函数，该函数也属于 NP 类。 那能有多难？

加密兄弟

起初，进展很快。 1981 年，Sipser 和两位合作者 证明 如果他们使用的电路对门的排列方式有一定的限制，那么某个布尔函数肯定很难计算。

“我们的幻想是，你将能够证明这些受限模型的相关内容，然后以你所学到的知识为基础，在越来越少的限制下进行工作，”西普瑟说。

1985 年，拉兹博罗夫迈出了下一步。 他刚刚开始在莫斯科读研究生，在解决另一个数学分支的问题时偶然加入了这一努力，结果证明解决 P 与 NP 问题是一个先决条件。

“我很幸运，我不知道这个问题有多困难，”拉兹博罗夫说。 “否则也许我根本就不会开始。”

Razborov 分析了仅包含 AND 和 OR 门的电路，并且 证明 无论门如何排列，使用这样的电路都很难计算特定的函数——而且，众所周知，该函数是 NP 完全函数。 为了解决 P 与 NP 问题，研究人员所要做的就是将 Razborov 的技术扩展到具有 NOT 门的电路。

拉兹博罗夫说：“有一种普遍的感觉，再迈一步，再出击，我们就会得到它。” 但事实并非如此。 拉兹博罗夫本人证明，如果不添加门，他的方法就会失败，而且没有人能找到其他前进的方法。 随着时间的流逝，他开始想知道为什么这条踪迹逐渐消失了。

在美国，鲁迪奇也在思考同样的问题。 他和因帕利亚佐是大学同学，后来一起读研究生。 他们的友谊是由于对哥德尔和图灵的自指证明及其对数学和计算机科学基础的影响的共同着迷而引发的。

“我们开玩笑说，我们将得到一个写着‘自我参考’的按钮，”因帕利亚佐说。

作为研究生，Rudich 和 Impagliazzo 都致力于密码学的复杂性理论基础，这门学科可能为尝试证明 P ≠ NP 提供了最佳的实践动机。 密码学家通过将秘密消息隐藏在“伪随机性”中来隐藏它们——以这种方式加密的消息对于任何窃听者来说都像是随机混乱的数字，但它仍然可以被预期的接收者解码。 但你如何确定潜在的窃听者会发现破解密码太困难了呢？

这就是复杂性理论的用武之地。当今最广泛使用的加密方法都是基于看似困难的 NP 问题——为了解密消息，攻击者需要一种尚未发现的快速算法来解决问题。 为了证明这些方法真正安全，您需要做的一件事是证明 P ≠ NP。 西普瑟说，如果没有证据，你所能做的就是“希望无论你试图向谁保守秘密，都不会是比你更好的数学家。”

虽然密码学本身就令人着迷，但它似乎与最初吸引鲁迪奇和因帕利亚佐进入该领域的自我参照论点相去甚远。 但当鲁迪奇努力理解为什么电路复杂性方法停滞不前时，他开始意识到这两个主题毕竟并没有那么遥远。 研究人员在试图证明 P ≠ NP 时所采用的策略具有弄巧成拙的特征，让人想起哥德尔的著名命题“这个陈述是无法证明的”——而密码学可以帮助解释原因。 在俄罗斯，拉兹博罗夫大约在同一时间发现了类似的联系。 这些是自然证明障碍的种子。

自然证明障碍的核心张力在于，区分高复杂性函数和低复杂性函数的任务类似于区分真随机性和用于加密消息的伪随机性的任务。 我们想证明高复杂度函数与低复杂度函数有明显不同，以证明 P ≠ NP。 但我们也希望伪随机性与随机性无法区分，以便对密码学的安全性充满信心。 也许我们不能两全其美。

一个残酷的笑话

1994 年，拉兹博罗夫和鲁迪奇意识到他们已经有了类似的见解，并开始共同努力将他们的结果结合起来。 他们首先观察到，之前所有使用电路复杂性证明 P ≠ NP 的尝试都采用了相同的一般策略：识别 NP 完全布尔函数的特殊属性，然后证明没有易于计算的函数可能共享该属性。 这表明所选的 NP 完全函数确实很难计算，证明 P ≠ NP。

Sipser、Razborov 和其他人成功地使用了同样的策略来证明他们更有限的结果，并且在每种情况下，研究人员发现的特殊属性是大多数布尔函数所共有的。 拉兹博罗夫和鲁迪奇创造了“自然证明”一词来指代这种财产被广泛共享的情况，仅仅是因为没有已知的替代方案。 如果“非自然”证明是可能的，它们就必须非常违反直觉，并且名副其实。

Razborov 和 Rudich 随后证明了他们的主要结果：P ≠ NP 的自然证明需要非常全面地了解易于计算和难以计算的函数之间的差异，并且这些知识还可以推动快速算法来发现容易计算的函数。 - 计算函数，即使它们表面上很复杂。 如果复杂性理论家成功地自然证明了 P ≠ NP，他们就会发现一种几乎万无一失的方法来浏览任意真值表并确定相应函数的电路复杂性是高还是低——这是一个比他们已经着手证明。

“你几乎情不自禁地得到了超出你预期的东西，”卡莫西诺说。

这就好像你试图对一个特定的陈述进行事实核查，但每一次尝试都变成了通用测谎仪的蓝图——这看起来好得令人难以置信。 对于复杂性理论家来说，自然证明的惊人力量同样让成功的可能性变得更小。 但如果这样的证明成功，由于电路复杂性和伪随机性之间的联系，意想不到的后果对密码学来说将是个坏消息。

要理解这种联系，想象一下查看具有许多输入变量的布尔函数真值表中的输出列，并将每个“真”替换为 1，将每个“假”替换为 0：

如果布尔函数具有很高的电路复杂性，那么原则上，这一长串输出将与真正随机的 0 和 1 字符串（例如，通过重复抛硬币获得的字符串）无法区分。 但如果函数的电路复杂度较低，则即使看起来很复杂，字符串也必须有简单、简洁的描述。 这使得它与密码学中使用的伪随机字符串非常相似，其简洁的描述就是隐藏在明显随机性中的秘密消息。

因此，Razborov 和 Rudich 的结果表明，P ≠ NP 的任何自然证明也将产生一种快速算法，可以区分包含隐藏消息的伪随机字符串和真正的随机字符串。 安全的密码学是不可能的——这与研究人员希望通过证明 P ≠ NP 所建立的理论恰恰相反。

另一方面，如果安全密码学是可能的，那么自然证明就不是证明 P ≠ NP 的可行策略——这是安全密码学的先决条件。 简而言之，这就是自然证明障碍。 复杂性理论家似乎遭遇了一个残酷的玩笑。

“如果你相信硬度，那么你就应该相信很难证明硬度，”卡巴内茨说。

进入元宇宙

P ≠ NP 猜想的含义与证明它的难度之间的联系很有趣，但很难确定。 一方面，自然证明障碍仅阻止了证明 P ≠ NP 的一种方法。 另一方面，它将证明 P ≠ NP 的困难与 P ≠ NP 本身联系起来，而是与安全密码学的存在联系起来——一个密切相关但不完全相同的问题。 为了真正理解这种联系，研究人员必须适应元复杂性。

“有这样的直觉，‘哦，因为 P ≠ NP，所以很难证明 P ≠ NP，’”威廉姆斯说。 “但为了理解这种直觉，你必须开始思考将 P ≠ NP 作为计算问题来证明的任务。”

这就是卡巴内茨作为研究生所做的事情。 他在乌克兰长大，苏联解体两年后完成了计算机科学本科学业。 在随后的混乱中，他几乎没有机会去追求他最感兴趣的理论课题。

“我想做一些更学术的事情，”卡巴内茨回忆道。 “而且我也很好奇想看看这个世界。” 他搬到加拿大读研究生，在那里他了解了自然证明障碍。 和卡莫西诺一样，卡巴内茨对这个结果非常着迷。 “你们之间的这种联系似乎非常深刻，”他说。

2000 年，在研究生学业即将结束时，他发现自然证据障碍在他与其他人的谈话中不断出现。 蔡金义，一位复杂性理论家，当时正在多伦多休假。 他们开始把这个障碍看作是一个邀请，而不是一个障碍——一个机会来准确地调查证明问题有多困难。 这 纸 他们提出的这一新观点将成为元复杂性这一新兴领域中最具影响力的早期著作之一。

Kabanets 和 Cai 的论文强调了 Razborov 和 Rudich 的自然证明障碍公式中隐含的计算问题：给定布尔函数的真值表，确定它的电路复杂性是高还是低。 他们将此称为最小电路尺寸问题（MCSP）。

MCSP 是一个典型的元复杂性问题：一个计算问题，其主题不是图论或其他外部主题，而是复杂性理论本身。 事实上，这就像 1980 世纪 XNUMX 年代推动复杂性理论家使用电路复杂性方法来解决 P 与 NP 问题的定量版本：哪些布尔函数难以计算，哪些容易计算？

“如果我们想出一种 MCSP 算法，那就像是一种自动化我们在复杂性理论中所做的事情的方法，”Impagliazzo 说。 “它至少应该让我们对如何更好地完成工作有深刻的了解。”

复杂性理论家并不担心这种神奇的算法会让他们失业——他们认为它根本不存在，因为拉兹博罗夫和鲁迪奇表明，任何这种用于区分高复杂性真值表和低复杂性真值表的算法都会使密码学成为可能不可能的。 这意味着 MCSP 可能是一个困难的计算问题。 但这有多难呢？ 它是 NP 完全的吗，就像哈密顿路径问题以及 1960 世纪 XNUMX 年代研究人员努力解决的几乎所有其他问题一样？

对于 NP 问题，“它有多难？” 通常很容易回答，但 MCSP 似乎是一个奇怪的异常值。 “我们很少有‘浮动’问题与这个 NP 完全问题岛无关，尽管它们看起来很难，”Kabanets 说。

卡巴内茨知道他和蔡并不是第一个考虑他们称之为 MCSP 问题的人。 苏联数学家从 1950 世纪 1960 年代开始研究了一个非常相似的问题，早期试图理解不同计算问题的内在难度。 Leonid Levin 在 XNUMX 世纪 XNUMX 年代末发展 NP 完备性理论时一直在努力解决这个问题，但他无法证明它是 NP 完备性的，而且他在没有它的情况下发表了他的开创性论文。

此后的 30 年里，这个问题很少引起人们的关注，直到 Kabanets 和 Cai 注意到它与自然证明障碍的联系。 卡巴内茨并没有指望自己解决这个问题——相反，他想探索为什么很难证明这个看似困难的计算难度问题实际上很困难。

“从某种意义上说，这是元-元-复杂性，”说 拉胡尔桑塔南，牛津大学复杂性理论家。

但它的硬度是否一直下降，或者至少有某种方式可以理解为什么研究人员未能成功证明 MCSP 是 NP 完全的？ Kabanets 发现，是的，这是有原因的：理解电路复杂性的困难就像任何已知的证明 MCSP NP 完备性的策略的障碍——这个问题本身就是理解电路复杂性的困难。 自然证明障碍的扭曲、弄巧成拙的逻辑似乎是不可避免的。

MCSP 也有可能不是 NP 完全的，但这似乎也不太可能——问题的某些更简单的变体已知是 NP 完全的。

“我们只是没有一个好的地方来放置它，使其与我们研究的所有其他问题直接相关，”因帕利亚佐说。

卡巴涅茨已经阐明了MCSP的奇怪行为，但他不知道如何取得进一步的进展。 元复杂性研究逐渐放缓。 16 年后，当研究人员发现与另一个基本问题之间存在令人惊讶的联系时，它再次蓬勃发展：如果你大多数时候只关心获得正确答案，那么解决问题有多难？

世界大战

对于日常问题，大多数时候有效的答案通常就足够好了。 例如，我们根据典型的交通模式来规划通勤，而不是针对最坏的情况。

大多数复杂性理论家都很难满足：如果他们能够找到一种快速算法，能够在每个可能的输入上获得正确的答案，他们只会满足于宣称问题很容易。 该标准方法根据研究人员所说的“最坏情况”复杂性对问题进行分类。 但还有一种“平均情况”复杂性理论，即如果有一种快速算法能够在大多数输入上获得正确答案，那么问题就会被认为很容易。

这种区别对于密码学家来说很重要。 想象一个几乎所有输入都可以轻松解决的计算问题，除了一些最佳算法失败的顽固情况之外。 最坏情况复杂性理论认为这是一个难题，但对于密码学来说它毫无用处：如果只有部分消息难以破译，那还有什么意义呢？

事实上，在莱文对 NP 完备性进行开创性工作十年后，他发起了对平均情况复杂性的严格研究。 在此期间，他与苏联当局发生了冲突——他是一个不敬的麻烦制造者，偶尔会破坏共产党青年团体的爱国活动。 1972年，他因明显的政治原因被拒绝获得博士学位。

“作为一名年轻的研究人员，要想在苏联取得成功，你就不能非常固执己见，很难想象列昂尼德不固执己见，”因帕利亚佐说。

Levin 于 1978 年移居美国，并在 1980 世纪 XNUMX 年代中期将注意力转向平均情况的复杂性。 他开始与其他人合作进一步发展这一理论，其中包括当时的研究生因帕利亚佐。 但即使取得了进展，因帕格利亚佐发现研究人员经常互相说三道四。 他想让每个人都达成共识，而莱文的论文以简洁着称，这并没有帮助他——那些 发起该领域 平均情况的复杂性不到两页长。

“我打算将列昂尼德的作品翻译成更容易理解的技术术语，”因帕利亚佐说。 他决定先对大局进行一个简短、有趣的概述，然后再深入数学计算。 “这占据了报纸的主导地位，而且这是人们唯一记得的部分。”

纸1995年出版，立即成为经典。 因帕格利亚佐 (Impagliazo) 为 五个世界 通过不同程度的计算难度和不同的加密能力来区分。 我们生活在其中一个世界，但我们不知道是哪一个。

自从因帕格利亚佐的论文发表以来，研究人员就梦想着消除他的微型多元宇宙的一部分——通过证明某些世界根本不可能存在来缩小可能性的空间。 有两个世界是特别诱人的目标：即使 P ≠ NP，密码学也不可能实现。

在其中一个称为 Heuristica 的世界中，所有 NP 完全问题在大多数输入上都很容易解决，但快速算法偶尔会犯错误，因此按照最坏情况复杂性理论的标准，这些问题仍然被认为是困难的。 这是一个密码学不可能实现的世界，因为几乎所有代码都很容易被破解。 在另一个被称为 Pessiland 的世界中，密码学之所以不可能实现，原因有所不同：从一般情况来看，每个问题都很困难，但对消息进行加密，即使对于预期的接收者来说，它也难以辨认。

事实证明，这两个世界与元复杂性问题密切相关——特别是 Heuristica 的命运与 MCSP 是否是 NP 完全性这一长期存在的问题有关。 很久以前让卡巴内茨着迷并困扰莱文的问题不仅仅是好奇心：整个世界都处于危险之中。

为了排除启发法，研究人员必须消除最坏情况和平均情况复杂性之间的区别——也就是说，他们必须证明任何在大多数输入上正确解决 NP 完全问题的假设算法实际上都可以解决它在所有情况下。 这种称为“最坏情况到平均情况减少”的联系已知在某些问题中存在，但它们都不是 NP 完全的，因此这些结果并不意味着任何更一般的情况。 消除启发式算法将帮助密码学家实现基于 P ≠ NP 单一假设的安全加密梦想。

但毁灭一个世界可不是一件小事。 2003年，两位复杂性理论家 显示 证明已知 NP 完全问题的最坏情况到平均情况减少的现有方法将意味着奇怪的后果，这表明这种证明可能是不可能的。

研究人员必须找到另一种方法，他们现在认为 MCSP 可能正是他们需要的问题。 但这在十多年后才变得清晰。 马可·卡莫西诺 (Marco Carmosino) 对自然证明屏障的持续着迷使人们第一次看到这种联系。

Carmosino 在研究生时期首次接触元复杂性研究 2013纸 由 Kabanets 和其他四位研究人员提出，进一步发展了 Kabanets 十多年前开创的自然证明屏障方法。 这更加坚定了他的信念，即从拉兹博罗夫和鲁迪奇的经典论文中还有更多东西值得学习。

“当时我对那篇论文很着迷，”卡莫西诺说。 “什么也没有变。”

在参观加州大学伯克利分校为期一个学期的研讨会期间，这种痴迷终于结出硕果，在那里他大部分时间都与 Impagliazo、Kabanets 和 安东尼娜·科洛科洛娃是纽芬兰纪念大学的复杂性理论家，他与 Kabanets 合作完成了 2013 年的论文。 卡莫西诺以前曾与他们三人合作过一次，这次成功的合作让他有信心向他们提出有关他最着迷的话题的问题。

“他以一种很好的方式骚扰人们，”卡巴内茨回忆道。

起初，Carmosino 对证明 MCSP 版本的 NP 完备性有新的想法，这些想法出现在 Razborov 和 Rudich 关于自然证明障碍的论文中。 但这些想法并没有成功。 相反，Impagliazzo 的即兴言论让四位研究人员意识到，自然证明障碍可以产生比任何人想象的更强大的算法——路障上刻有一张秘密地图。

在一个 2016纸四位研究人员证明，某种平均情况 MCSP 算法可用于构建最坏情况算法，用于识别隐藏在看似随机的数字字符串中的模式——计算机科学家将这项任务称为“学习”。 这是一个惊人的结果，因为直观学习似乎比 MCSP 算法执行的二元分类任务（高复杂性或低复杂性）更困难。 而且，令人惊讶的是，它将一项任务的最坏情况复杂性与另一项任务的平均情况复杂性联系起来。

“这种联系根本不存在，这一点并不明显，”因帕利亚佐说。

MCSP 的快速算法纯粹是针对一般布尔电路的假设：除非 MCSP 被证明是一个简单的计算问题，否则它不可能存在，尽管所有证据都相反，这意味着四位研究人员的论文所暗示的学习算法是同样是假设的。

但对于 MCSP 的一些更简单版本（当电路有特定限制时区分高复杂性真值表和低复杂性真值表），快速算法已经众所周知很多年了。 Carmosino、Impagliazzo、Kabanets 和 Kolokolova 的论文表明，这些算法可以转化为同样受到限制的学习算法，但仍然比研究人员之前在如此严格的理论水平上理解的任何算法更强大。

“不知何故，它们的自我参照风格使你能够做一些看似更标准的问题无法做到的事情，”伊兰戈说。

这一结果引起了研究其他主题的复杂性理论家的注意。 这也是未来几年将出现的元复杂性和平均情况复杂性之间进一步联系的预览。

最重要的是，这证明了研究人员通过提出一些简单的问题可以取得多大的进展，这些问题一开始似乎只是阻碍了他们的进步。

“这种二元性是至少过去 30 或 40 年复杂性的一个主题，”因帕利亚佐说。 “障碍往往也是机遇。”

部分分数

自从卡莫西诺和他的同事发表论文以来，进展只是在加速。

“新的事情正在发生，”科洛科洛娃说。 “有很多非常非常聪明的初级研究人员。”

Ilango 是这些年轻的研究人员之一——在研究生院的头三年，他使用双管齐下的策略解决了证明 MCSP NP 完备性这一令人畏惧的开放性问题：证明 NP 完备性 简单 版本 正如电路复杂性研究人员在 1980 世纪 XNUMX 年代攻击 P 与 NP 时所做的那样，同时还证明了 MCSP 的 NP 完整性 更复杂的版本，直观上看起来更难，因此也许更容易证明困难。

Ilango 将他对元复杂性的兴趣归功于 埃里克·阿伦德是罗格斯大学的复杂性理论家，也是 2000 年代和 2010 年代初期继续研究元复杂性的少数研究人员之一。 “他的热情很有感染力，”伊兰戈说。

另一位受阿伦德启发的年轻研究人员是 平原秀一现任东京国立信息研究所教授。 2018 年，平原还是一名研究生，他揭示了 Carmosino 和他的合著者发现的元复杂性和平均情况复杂性之间关系的真实程度。 这四位研究人员发现了一个问题（MCSP）的平均情况复杂性与另一个问题（布尔学习）的最坏情况复杂性之间的联系。 平原进一步发展了他们的技术 漂移 MCSP 的最坏情况到平均情况的减少。 他的结果表明，像 Carmosino 和他的同事所考虑的那样的假设平均情况 MCSP 算法实际上足够强大，可以解决稍微不同版本的 MCSP，而不会犯任何错误。

Hirahara 的结果令人兴奋，因为许多研究人员怀疑 MCSP 是 NP 完全的，这与已知从最坏情况到平均情况减少的所有其他问题不同。 如果他们能够扩展 Hirahara 的结果以涵盖所有平均情况算法，然后证明 MCSP 是 NP 完全的，那将证明我们并不生活在 Heuristica 中。

“这确实会是一个惊天动地的结果，”桑塔南说。

证明 MCSP 是 NP 完全的似乎是一项艰巨的任务 - 毕竟这个问题已经开放了 50 多年。 但经过一个 突破 去年，Hirahara 提出，研究人员现在比几年前任何人预期的都要接近得多。

Hirahara 证明了问题的一个变体（称为部分 MCSP）的 NP 完备性，在该变体中，您忽略每个真值表中的某些条目。 他的证明基于 Ilango 开发的方法，表明部分 MCSP 相当于一个看似无关的问题，涉及一种称为秘密共享的加密技术。 这是一种将加密消息分给多人的方法，这样只有当他们中的某一部分一起工作时才能解码该消息。

对于密码学中的任何实际应用，您都想提前知道这个分数，但借助额外的密码技巧，您可以构建一个令人沮丧的场景，在该场景中很难弄清楚有多少人需要合作。 Hirahara 找到了一种方法来证明这个人为的密码问题是 NP 完全的，然后表明该证明也暗示了部分 MCSP 的 NP 完全性。

这一结果比 Hirahara 的早期工作更加激发了元复杂性研究人员的活力，其他研究人员也注意到了——复杂性理论家兼博主兰斯·福特诺 (Lance Fortnow) 将其称为“ 今年的结果。 这是因为解决此类“部分函数”版本的计算问题一直是其他 NP 完整性证明中的关键中间步骤。

“这是一项了不起的工作，”威廉姆斯说。 “每个人都认为这些部分问题与完整问题的难度大致相同。”

证明 MCSP 完整版本的 NP 完整性仍然存在障碍。 但没有一个障碍表明需要一个全新的工具包——这可能只是找到结合已知技术的正确方法的问题。 一个证明将最终解决自复杂性理论存在以来就一直抵制分类的少数问题之一的地位。 莱文在电子邮件中写道：“这会让我感到羞愧，因为我没有看到它，所以我很愚蠢:-)。”

缺失的部分

MCSP 甚至不是唯一引发重大突破的元复杂性问题。 2020 年，康奈尔科技大学密码学家 拉斐尔山口 和他的研究生 刘彦一 发现了一个连接 不同的元复杂性问题和基本密码协议之间的界限，该协议定义了 Heuristica 和 Pessiland 之间的边界，Pessiland 是 Impagliazzo 世界中最糟糕的世界（其中 NP 完全问题在平均情况下很难，但密码学仍然是不可能的）。 这使得他们研究的问题成为攻击佩西兰的主要候选问题，并且他们的研究 最近的工作 表明它也可以对抗 Heuristica。

“拼图的不同部分缺失了，”帕斯说。 “对我来说，这些领域如此紧密地联系在一起真是太神奇了。”

平原警告说，想要剔除 30 年前因帕格利亚佐想象的世界的研究人员仍然面临着挑战。 “我想说，在某个时候 Heuristica 和 Pessiland 将被排除，但我不确定我们距离有多近，”他说。

许多研究人员预计，最大的困难将是弥合两种不同的平均情况复杂性模型之间看似无害的差距。 密码学家通常研究在两个方向上都会出错的平均情况算法，有时会将随机字符串错误地标记为伪随机，反之亦然。 与此同时，Hirahara 的最坏情况到平均情况的减少也适用于仅产生第一类错误的平均情况算法。 像这样的微妙区别可以使复杂性理论产生巨大的差异。 但尽管存在这个障碍和许多其他障碍，阿伦德还是忍不住表现出了谨慎的乐观态度。

“我尽量不让自己过于相信，因为有一个相当完善的记录表明没有任何效果，”他说。 “但我们看到了许多真正令人兴奋的进展——克服看似障碍的方法。”

如果说研究人员从回答 P 与 NP 问题（甚至只是理解它）的斗争中学到了一个教训，那就是复杂性理论本身就是复杂的。 但正是这种挑战让这项任务变得如此有意义。

“这实际上是一件很棒的事情，但它是如此困难，”卡莫西诺说。 “我永远不会感到无聊。”

编者注：斯科特·阿伦森 (Scott Aaronson) 是 广达杂志“ 顾问委员会.