裁决中的P与NP以及复杂性的复杂度_

作者：Benjamin Skuse

译者：zzllrr小乐

如果我请你出庭作证，对一长串数字按照从低到高的顺序进行排序，与解决一个巨大的数独难题一样复杂，你可能会认为我已经失去了理智。你肯定会质疑为什么纳税人的钱被浪费在一个无聊主题的审判上。

然而，将案件告上法庭可能比第一印象所认为的更有价值。判定此类任务的相对难度这种基础性难题是数学和计算机科学中最致命的问题之一：P与NP问题，自1971年提出以来一直悬而未决。这个问题的解决对现实世界产生巨大影响，影响医学、人工智能、互联网安全和许多其他领域。由于这些原因，P与NP问题是克莱数学研究所选出的我们这个时代最重要的七大千禧年奖问题之一。

民事案件

P与NP中的“P”代表“多项式时间”（Polynomial time）。当你增加输入的大小时，如果（理想版本的）计算机需要相应成比例更长一些的时间来完成其给定的任务，那么这个计算机程序就是以多项式时间运行。列表排序是P问题的一个完美示例，其中有已知且简单的方法对列表进行排序并验证列表是否正确排序，并且不会随着列表长度的增加而以某种荒谬的增长速度消耗时间。

图释：对于可以在多项式时间内解决的问题（例如O(n)、O(n²)），随着输入的增大，难度如何以合理的速度增长，以及解决其他问题的难度如何以加速的速度增长（例如 O(2ⁿ), O(n!)）

展开P与NP的“NP”信息量较少（郑重声明，它代表“非确定性多项式时间”，Nondeterministic Polynomial time），但从本质上而言，NP问题虽然很难解决，但很容易验证。数独的通用版本 - 不是使用9×9网格，而是允许任意大（n²×n²）的网格 - 是一个NP问题。没有已知的方法可以比蛮力检查每个可能填充棋盘的数字组合来更快地解决这个问题。因此，当你增加n时，解决谜题的时间会以指数方式增长；也就是说，它变得非常难以解决，而且难度非常快地增长。然而，验证解所用的时间仍然是多项式级别的，因为你可以运行相对简单且快速的算法来检查所有行、列和宫中输入的数字是否遵循所有规则；即它仍然很容易验证。

将你现在所了解的P与NP问题与列表排序联系起来，并解决一个巨大的数独难题，哪个更难解决的问题的答案似乎更加明显 – 毫无疑问是列表排序！如果你随后将同样的思路应用于大量P问题和NP问题，并在民事法庭上陈述你的发现，那么很容易证明——基于概率的平衡——所有列表排序——类型问题并不等同于所有大型数独类问题，即P≠NP，你会轻松赢得官司。

刑事案件

图源：Nick Youngson CC BY-SA 3.0 Alpha Stock Images

但数学家和计算机科学家需要比这更高的证明标准。事实上，社会对证明标准的要求比这更高。因为如果P确实等于NP，原则上，目前棘手的问题就会变得容易。这一事实可以用来做好事——例如优化运输路线和寻找新药物——也可以用来做坏事，包括黑客入侵银行账户和政府网站。就像刑事法庭的陪审团确定被告有罪一样，我们都需要“排除合理怀疑”（beyond reasonable doubt）来知道P=NP是否成立。这是一个更加艰难的提议。

为了实现这一目标，研究人员已经证明，几乎所有看似困难的NP问题都是“NP完全”（NP-complete）的，这意味着如果他们对一个NP完全问题有一个有效的解，那么它也可以适用于快速解决所有其他NP问题。例如，广义数独是NP完全的，因为它可以简化为其他已知为NP完全的经典复杂问题，包括（明显相似的）拉丁方完备（LSC，Latin square completion）问题和（表面上看非常不同的）哈密顿环路（Hamiltonian cycle）问题。从精确的数学意义上来说，它们是等价的。

因此，为了证明P是否等于NP，勇敢的研究人员所要做的就是发现一种巧妙的算法技巧，可以在多项式时间内解决NP完全问题（P = NP），或者只需找到一个他们可以证明任何计算机程序都无法快速解决的NP完全问题（P ≠ NP）。然而，尽管一些最聪明的人经过半个世纪的努力，这两条路仍然难以捉摸。

复杂问题的复杂度

近年来，许多研究人员不再尝试直接求解P与NP问题。相反，他们一直在质疑解决P与NP以及类似问题一开始就很困难的原因。他们一直在问诸如“确定各种计算问题的难度有多难？”之类的问题。以及“为什么很难确定它们有多困难？”这些及其他“元”问题是数学和计算机科学领域称为“元复杂度”（meta-complexity）的基础。既是一个研究主题，也是研究人员试图用来解决P与NP等问题的工具。

目前元复杂度研究人员的一个重要关注点是一个历史悠久且仍然无法明确分类的特殊问题：最小电路门数问题（MCSP，Minimum Circuit Size Problem）。MCSP之所以有趣有几个原因，尤其是因为它是少数具有挑战性的计算复杂度问题之一，目前尚不清楚它是否是NP完全的。

MCSP被发现在密码学、证明复杂度、学习理论和电路下界等不同领域发挥着核心作用，它提出的问题是：你能确定用于计算布尔函数的黑盒假设计算机具有高的还是低的电路复杂度吗？布尔函数将一定数量的0或1作为输入，并输出0或1（真或假）。由此，你可以构建一个真值表：输入值及其相应输出的所有组合的表格化的表示。本质上，真值表提供了函数的输入输出行为，但没有提供有关函数计算复杂度的信息。这种复杂度用电路复杂度来表示，电路复杂度定义为构建可以计算给定函数的最小电路所需的逻辑门总数。

有了这些澄清，问题就可以更精确地提出：MCSP将布尔函数f的描述看作输入一个真值表以及电路门数参数s，并询问“是否存在一个计算f的门数≤s的的电路？”由于MCSP既具有计算方面的复杂度，又与复杂度的计算有关，因此它作为元复杂度的元问题，即元²-复杂度问题并不常见。事实上，研究人员正在试图找出为什么很难确定MCSP的解决难度，这意味着它可能更具元性；也许是一个元³-复杂度问题。

对于最简单的布尔函数，MCSP可以通过在多项式时间内运行的算法来求解。但随着函数变大，绝大多数函数似乎需要指数级增加的逻辑门数量。与广义数独一样，MCSP似乎不可能解决，除非使用蛮力搜索，但如果给出一个解，也很容易验证。你可以猜测一个电路，运行每个可能的输入，然后查看输出是否与给定布尔函数的输出匹配。因此，这显然是一个NP问题。但P里也有吗？它是一个NP完全问题吗？即，解决它的快速方法是否意味着证明NP中的所有问题实际上都在P中？社区中的许多人怀疑MCSP不在P中，而是NP完全的，如果得到证实，则明确意味着P ≠ NP。

解的进展？

近年来，研究人员在证明MCSP是NP完全的这一方面取得了重大进展。例如，大量证据（其中许多是在过去六年中出现的）表明MCSP的变体是NP完全的。也许最有趣的一些进展是来自东京国家信息研究所的Shuichi Hirahara（平原秀一）取得的。

2018年，Hirahara将MCSP从最坏情况化简为平均情况。在这里，“平均情况”复杂度是衡量大多数输入问题的平均容易程度或困难程度的指标，而“最坏情况”复杂度是标准方法，考虑到所有可能输入的问题的最大复杂度。复杂度对于平均情况和最坏情况可能不同的问题很有趣，因为它们可以提供对这些问题的基本复杂度的见解。Hirahara的结果意味着，假设的平均情况MCSP算法实际上足够强大，可以解决稍微不同的MCSP版本，该版本限制了允许的电路类型，而不会犯任何错误。这个结果令人兴奋，因为没有其他NP完全问题具有已知的最坏情况到平均情况的减少。鉴于所有NP完全问题的等价性，它为研究P与NP问题提供了新的途径。

接下来，在2022年，Hirahara利用复杂度理论和先进信息论密码学的结合，证明了部分布尔函数上的MCSP是NP难的（NP难问题与NP完全问题一样难，但不一定必须在NP中）。部分布尔函数有一个真值表，其中包含常见的0和1，但也包含一些“不知道”符号 - 有些可能是0或1，你并不关心电路是怎样的。不知何故，添加这种“不知道”的模糊性允许部署许多有用的技术来解决部分MCSP问题，但到目前为止，尚不清楚是否可以应用这些相同的技术来解决原始MCSP问题。

P、NP、NP完全和NP困难等问题集的欧拉图（Euler diagram）。左侧在P ≠ NP的假设下有效，而右侧在P = NP的假设下有效。图源：Behnam Esfahbod

另一位研究人员，来自麻省理工学院的Rahul Ilango（拉胡尔·伊兰戈），一直致力于以多种方式证明MCSP的NP完全性，将MCSP的更简单和更复杂的版本视为解决主要问题的切入点。他最新的元复杂度结果成功地将 MCSP与看似不同的布尔可满足性问题（SAT）联系起来，其中将获得布尔函数作为公式或电路的表示，并询问有关其函数的信息（例如，它是否具有其真值表中的 1，或者它输出某种0和1的模式，等等）。

MCSP就是所谓的“黑盒问题”，因为在给定黑盒访问的情况下，你想了解有关表示的一些信息。布尔可满足性问题则完全不同。布尔可满足性问题（SAT）被称为“白盒问题”，其目标是根据函数的表示来说明有关该函数的一些信息。2023年，Ilango和同事做出了惊人的发现，即SAT通过随机预言简化为MCSP，即具有可在P中计算且可供所有电路和计算机访问的完全随机函数。由于SAT众所周知是NP完全的，因此具有随机预言的MCSP也必须是NP完全的。

这些和其他最近的结果进一步证明了原始MCSP实际上也是NP完全的。而且，如果这是真的，MCSP可以隐藏缺失的证据，“排除合理怀疑”地证明P是否等于NP。

就像问题本身一样，P与NP的裁决当然是复杂而漫长的，但正在取得进展，而且感觉研究人员终于离结论越来越近了。