复杂性理论探索知识极限的 50 年历程 - Ben Brubaker

一，起源

二，障碍

三，机遇

证明问题难以解决有多难？几十年来，元复杂性理论家们一直在提出这样的问题。最近的一系列成果开始给出答案。

复杂性理论家们正面临着迄今为止最令人费解的问题：复杂性理论本身。

一，起源

2007 年秋季学期的第一周，Marco Carmosino拖着疲惫的身躯来到University of Massachusetts, Amherst计算机科学专业的一堂数学课前，Carmosino读大二，正在考虑退学去设计电子游戏。这时，教授提出了一个简单的问题，这个问题改变了他的人生轨迹：你怎么知道数学真的有用？

Carmosino现在是 IBM 的理论计算机科学家，他回忆道，“这让我坐起来并引起注意”，他报名参加了一个关于库尔特-哥德尔（Kurt Gödel）工作的选修研讨会，哥德尔令人眼花缭乱的自指论证首次揭示了数学推理的极限，并为未来所有关于计算基本极限的工作奠定了基础，这让我受益匪浅。

卡莫西诺说：“我百分之百不明白，但我知道我想明白。”

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

尽管计算复杂性理论（研究不同问题的内在难度）领域的研究人员付出了数十年的努力，但 P versus NP 问题的解决方案仍然遥遥无期，甚至不知道应该从哪里开始证明。

麻省理工学院资深复杂性理论家迈克尔-西普瑟（Michael Sipser）说：“没有路线图，这就像你要进入荒野一样。”

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

Rahul Ilango，麻省理工学院的研究生，他在该领域取得了一些最令人兴奋的最新成果，说：“你可能会想，好吧，这有点酷，也许复杂性理论家们都疯了。”

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

Scott Aaronson，德克萨斯大学奥斯汀分校的复杂性理论家说： “很明显，元复杂性是事物的核心。”

这就是研究人员从 P versus NP 问题走向元复杂性的漫长而曲折的故事。这并不是一段轻松的旅程--道路上布满了错误的转弯和路障，它一次又一次地自我循环。然而，对于元复杂性研究人员来说，进入未知领域的旅程本身就是一种奖励。Valentine Kabanets，加拿大西蒙弗雷泽大学（Simon Fraser University）的复杂性理论家说，从提出看似简单的问题开始， “你根本不知道会走到哪里”。

已知的未知

复杂性理论家习惯于将计算问题划分为宽泛的“复杂性类别”，这些类别的标签让人联想到纳斯达克股票代码。计算问题原则上可以通过算法（精确指定的指令列表）来解决。但并非所有算法都同样有用，算法之间的差异暗示了不同类别问题之间的根本差异。复杂性理论家面临的挑战是将这些提示转化为关于复杂性类别之间关系的严格定理。

这些关系反映了关于计算的永恒不变的真理，远远超越了任何特定的技术。 Kabanets说：“这就像发现了宇宙法则。”

P 和NP是数以百计的复杂性类别中最著名的两个。粗略地说，P 是一类很容易解决的问题，比如按字母顺序排列列表。NP 是一类容易检查解决方案的问题，比如数独谜题。由于所有容易解决的问题也容易检查，所以 P 类问题也属于 NP 类。但是，有些 NP 问题似乎很难解决—如果不先尝试多种可能性，你就无法立即直觉出数独谜题的解。会不会这种表面上的困难只是一种假象--每一个容易检查的问题都有一个简单的解题技巧？

如果是这样，那么 P = NP：两类等价。如果是这样的话，那么一定有某种算法能让我们轻松解决巨大的数独谜题、优化全球航运路线、破解最先进的加密技术以及自动证明数学定理。如果P≠NP，那么许多原则上可以解决的计算问题实际上将永远无法解决。

早在 P versus NP 问题被首次提出之前，研究人员就曾担心过形式数学推理的局限性，事实上，这比现代计算机科学的诞生还要早得多。1921 年，数学家大卫-希尔伯特（David Hilbert）提出了一项研究计划，希望将数学建立在绝对确定性的基础上。他希望从几个简单的假设（称为公理）出发，推导出符合三个关键标准的统一数学理论。

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

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

研究人员仍然希望，未来的数学理论虽然必然是不完备的，但仍有可能被证明是可解的。也许他们可以开发出一些程序，既能识别所有可证明的语句，又能避开像哥德尔这样令人头疼的命题。问题是，没有人知道如何推理这些假设的程序。

1936 年，年仅 23 岁的研究生阿兰-图灵用当时并不熟悉的计算语言重新表述了希尔伯特的可判定性条件，给了希尔伯特致命一击。图灵建立了一个数学模型—现在被称为图灵机—它可以表示所有可能的算法，并证明如果希尔伯特的程序存在，它就会符合这个模型。然后，他利用哥德尔的自指方法证明了不可判定语句的存在--或者说，任何算法都无法解决的不可计算问题。

希尔伯特的计划毁于一旦： 什么问题可以被证明，什么问题可以被计算，这些都将永远存在根本性的限制。但是，随着计算机从理论抽象发展为真正的机器，研究人员意识到图灵对可解和不可解问题的简单区分留下了许多未解之谜。

到 20 世纪 60 年代，计算机科学家已经开发出解决某些问题的快速算法，而对于另一些问题，唯一已知的算法却慢得惊人。如果问题不仅仅在于问题是否可以解决，而是在于解决这些问题的难度有多大？·

Carmosino说： “一个丰富的理论出现了，而我们不知道答案。”

殊途同归

为了说明难度问题有多么令人困惑，让我们来考虑一对密切相关的图形问题。图是由点（称为节点）和线（称为边）连接而成的网络。计算机科学家用它们来模拟从量子计算到交通流量的一切

1971 年，复杂性理论家斯蒂芬-库克（Stephen Cook）在美国被剥夺终身教职后搬迁到多伦多大学，不到一年就发表了一项非凡的成果。他发现一个特殊的 NP 问题有一个奇怪的特征： 如果有一种多项式算法能解决这个问题，那么它也能解决 NP 中的所有其他问题。库克的“通用”问题，似乎是支撑这一类看似困难的问题的一根孤柱，将它们与下面的简单问题区分开来。破解了这一个问题，NP 的其他问题就会轰然倒塌。

库克怀疑他的普遍性问题没有快速算法，他在论文中途如是说，并补充说：“我觉得值得花相当大的努力去证明这个猜想。 ” 事实证明，“相当大的努力”是轻描淡写的。

大约在同一时间，苏联一位名叫列昂尼德-列文（Leonid Levin）的大学生也证明了类似的结果，只不过他发现了几个不同的普遍性问题。此外，美国复杂性理论家理查德-卡普（Richard Karp）也证明了库克（虽然卡普和库克直到多年后才知道列文的研究成果）所确定的普遍性属性本身就是普遍的。几乎每一个没有已知多项式算法的 NP 问题--也就是说，几乎每一个看起来很难的易于检查的问题--都具有相同的性质，这就是后来的 NP-完备性。

这意味着所有的 NP完全问题--哈密尔顿路径问题、数独和成千上万的其他问题--在精确意义上都是等价的。Ilango 说，“你有所有这些不同的自然任务，而它们都神奇地变成了相同的任务，但我们仍然不知道，同样的任务是否可能完成。”

解决任何 NP完全问题的难度都足以解决P versus NP问题。如果P≠NP，那么简单问题和困难问题之间的区别就会被成千上万根同样坚固的柱子支撑起来。如果 P = NP，整座大厦就会在倒塌的边缘摇摇欲坠，只等一块碎片掉下来。

库克、莱文和卡普将许多看似毫不相干的问题统一了起来。现在，复杂性理论家们只需解决一个问题：P = NP 与否？

五十年后，这个问题依然没有答案。 Kabanets把对计算极限的推理比作在没有大局意识的情况下勘测广袤的领土。一个拥有无限计算能力的人可以从山顶俯瞰全局，但凡人无法指望这种优势。 他说：“我们这些在山脚下的人可以试着跳上跳下，以获得更好的视野。”

假设 P = NP。要证明这一点，研究人员需要为一个 NP-完全问题找到一种快速算法，而这种算法可能就隐藏在这片广袤土地上某个不起眼的角落里。谁也不能保证他们很快就能找到： 复杂性理论家们偶尔也会在几十年的工作之后，才发现一些看似很难（虽然不是 NP-complete）的问题的巧妙算法。

现在假设 P ≠ NP。证明这一点似乎更加困难。复杂性理论家们必须证明，不可能存在任何快速算法，这实际上预料到并挫败了所有未来研究者的最大努力。

不知道从何入手是问题的一部分，但研究人员并非没有尝试过，几十年来，他们从多个角度攻克了这一难题，却发现每一次转折都会阻挡他们前进的道路。 卡莫西诺说：“这是理论计算机科学中最明显的事实之一，当你遇到一个如此持久的现象时，你需要一些解释。”

二，障碍

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

卡莫西诺回忆说：“我当时想，’哇，我得认真对待这个问题’”。没过多久，他就对这门学科爱不释手，以至于他的导师温和地建议他重新考虑毕业后的计划。

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

起初，卡莫西诺的主要目标是更好地理解二十年前一篇让他浮想联翩的里程碑式论文。这篇论文是由复杂性理论家Alexander Razborov和Steven Rudich撰写的，论文指出，证明 P ≠ NP 的某种“自然”策略几乎肯定会失败，因为成功需要付出巨大的代价—密码学彻底崩溃--而研究人员认为这种可能性微乎其微。研究人员将拉兹伯洛夫和鲁迪奇的结果解释为这种证明 P ≠ NP 的流行方法的障碍。

这个“自然证明障碍”只是解决复杂性理论公开问题的众多已知障碍之一。每一个障碍都像一个路障，警告人们一条看似有希望的道路实际上是一条死胡同。这些障碍共同表明，任何能解决 P versus NP 问题的证明都必须与过去使用的任何证明截然不同；这就是为什么大多数研究人员认为解决方案仍然遥遥无期。不过，至少这些障碍告诉他们不要往哪里找。

Ilango 说：“复杂性理论既受到诅咒，又受到祝福，因为它有如此之多的障碍。”

当卡莫西诺遇到自然证明障碍时，已经有近 20 年的历史了。但他怀疑这对研究人员来说还有更多的启示，有一天，当他和三位同事从元复杂性的角度研究自然证明障碍，证明了一个令人惊讶的结果时，他的这种感觉得到了证实。他们的证明是引发人们对元复杂性新兴趣的几项重要成果之一，在过去几年中取得了一系列进展。

不过，要想从自然证明障碍追溯到元复杂性，我们还得回到 20 世纪 70 年代研究人员首次开始解决 P versus NP 问题的地方，是什么让证明问题变得如此困难？

迂回曲折的道路

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

在密歇根州北部一个小镇长大的香农似乎不太可能成为信息时代的开创者，然而，他却体现了计算机科学这一新兴学科的跨学科性质，在电气工程和数理逻辑领域同样游刃有余。在他的硕士论文中，香农展示了由机电开关组成的电路如何表示涉及布尔变量的逻辑表达式，布尔变量是指只能取两个值（如真或假，或 1 和 0）的量。

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

“当你看你的电脑时，它到底在做什么？它在运行一个电路， ”Ilango 说。

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

电路复杂性框架要求重新思考图灵计算模型中最基本的概念。在这里，研究人员考虑的不是计算问题和解决这些问题的算法，而是布尔函数和计算这些函数的电路。布尔函数接收布尔变量--真和假、1 和 0--并输出真或假、1 或 0。 与算法一样，电路描述了在任意输入条件下产生输出的过程。

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

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

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

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

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

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

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

三，机遇

Carmosino 在研究生时期首次接触元复杂性研究是通过 Kabanets 和其他四位研究人员 2013 年发表的一篇论文，该论文进一步发展了 Kabanets 十多年前开创的解决自然证明障碍的方法。 这更加坚定了他的信念，即从Razborov和Rudich的经典论文中还有更多东西值得学习。

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

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

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

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

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

Impagliazzo说：“这种联系根本不存在，这一点并不明显。”

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

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

Ilango说：“不知何故，它们的自指风格使你能够做一些看似更标准的问题无法做到的事情。”

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

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

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

部分分数

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

“新的事情正在发生，” Kolokolova说。 “有很多非常非常聪明的年轻研究人员。”

Ilango 是这些年轻的研究人员之一 - 在研究生院的前三年，他使用双管齐下的策略解决了证明 MCSP NP 完备性这一令人畏惧的开放性问题：作为电路复杂性研究人员，证明 MCSP 的简单版本的 NP 完备性 在 20 世纪 80 年代攻击 P versus NP 时就这样做了，同时也证明了更复杂版本的 NP 完备性，这些版本直观上看起来更难，因此可能更容易证明困难。

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

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

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

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

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

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

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

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

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

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

缺失的部分

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

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

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

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

原文：

Complexity Theory’s 50-Year Journey to the Limits of Knowledge

By BEN BRUBAKER，August 17, 2023

https://www.quantamagazine.org/complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/