注：本文为 “P/NP 问题” 相关合辑。
图片清晰度受引文原图所限。
略作重排，如有内容异常，请看原文。

---

著名的 P = NP 问题到底是什么？

Matrix67 Python猫 2022年08月05日 10:00 江苏

PS：以下内容为作者 2006 年及 2022 年两篇文章合并而成，为便于阅读，内容略有改动。

作者：Matrix67
来源：http://www.matrix67.com/blog/archives/105

引言

你经常会看到网上出现“这怎么做，这不是 NP 问题吗”“这个只有搜了，这已经被证明是 NP 问题了”之类的话。这或许是众多 OIer 最大的误区之一。你要知道，大多数人此时所说的 NP 问题其实都是指的 NPC 问题。他们没有搞清楚 NP 问题和 NPC 问题的概念。NP 问题并不是那种“只有搜才行”的问题，NPC 问题才是。

时间复杂度的概念

时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有 $O(1)$ 的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是 $O(n)$，比如找 $n$ 个数中的最大值；而像冒泡排序、插入排序等，数据扩大 2 倍，时间变慢 4 倍的，属于 $O(n^2)$ 的复杂度。

还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是 $O(a^n)$ 的指数级复杂度，甚至 $O(n!)$ 的阶乘级复杂度。不会存在 $O(2\cdot n^2)$ 的复杂度，因为前面的那个“2”是系数，根本不会影响到整个程序的时间增长。同样地，$O(n^3+n^2)$ 的复杂度也就是 $O(n^3)$ 的复杂度。

因此，我们会说，一个 $O(0.01\cdot n^3)$ 的程序的效率比 $O(100\cdot n^2)$ 的效率低，尽管在 $n$ 很小的时候，前者优于后者，但后者时间随数据规模增长得慢，最终 $O(n^3)$ 的复杂度将远远超过 $O(n^2)$。我们也说，$O(n^{100})$ 的复杂度小于 $O(1.01^n)$ 的复杂度。

多项式级复杂度与非多项式级复杂度

容易看出，前面的几类复杂度被分为两种级别，其中后者的复杂度无论如何都远远大于前者：一种是 $O(1)$，$O(\log n)$，$O(n^a)$ 等，我们把它叫做多项式级的复杂度，因为它的规模 $n$ 出现在底数的位置；另一种是 $O(a^n)$ 和 $O(n!)$ 型复杂度，它是非多项式级的，其复杂度计算机往往不能承受。

当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，往往会超时，除非是数据规模非常小。

不可解问题与问题的分类

自然地，人们会想到一个问题：会不会所有的问题都可以找到复杂度为多项式级的算法呢？很遗憾，答案是否定的。有些问题甚至根本不可能找到一个正确的算法来，这称之为“不可解问题”(Undecidable Decision Problem)。The Halting Problem 就是一个著名的不可解问题。

有人说，这样的“问题”不是一个“正规”的问题，正规的问题是让程序解决一个问题，输出一个“YES”或“NO”（这被称为判定性问题），或者一个什么什么的最优值（这被称为最优化问题）。那么，根据这个定义，我也能举出一个不大可能会有多项式级算法的问题来：Hamilton 回路。

问题是这样的：给你一个图，问你能否找到一条经过每个顶点一次且恰好一次（不遗漏也不重复）最后又走回来的路（满足这个条件的路径叫做 Hamilton 回路）。这个问题现在还没有找到多项式级的算法。事实上，这个问题就是我们后面要说的 NPC 问题。

P 类问题、NP 类问题与 NPC 类问题

P 类问题

下面引入 P 类问题的概念：如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于 P 问题。 P 是英文单词多项式的第一个字母。哪些问题是 P 类问题呢？通常 NOI 和 NOIP 不会出不属于 P 类问题的题目。我们常见到的一些信息奥赛的题目都是 P 问题。道理很简单，一个用穷举换来的非多项式级时间的超时程序不会涵盖任何有价值的算法。

NP 类问题

接下来引入 NP 问题的概念。这个就有点难理解了，或者说容易理解错误。在这里强调（回到我竭力想澄清的误区上），NP 问题不是非 P 类问题。NP 问题是指可以在多项式的时间里验证一个解的问题。NP 问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。

比方说，我 RP 很好，在程序中需要枚举时，我可以一猜一个准。现在某人拿到了一个求最短路径的问题，问从起点到终点是否有一条小于 100 个单位长度的路线。它根据数据画好了图，但怎么也算不出来，于是来问我：你看怎么选条路走得最少？我说，我 RP 很好，肯定能随便给你指条很短的路出来。然后我就胡乱画了几条线，说就这条吧。那人按我指的这条把权值加起来一看，嘿，神了，路径长度 98，比 100 小。于是答案出来了，存在比 100 小的路径。别人会问他这题怎么做出来的，他就可以说，因为我找到了一个比 100 小的解。

在这个题中，找一个解很困难，但验证一个解很容易。验证一个解只需要 $O(n)$ 的时间复杂度，也就是说我可以花 $O(n)$ 的时间把我猜的路径的长度加出来。那么，只要我 RP 好，猜得准，我一定能在多项式的时间里解决这个问题。我猜到的方案总是最优的，不满足题意的方案也不会来骗我去选它。这就是 NP 问题。

当然有不是 NP 问题的问题，即你猜到了解但是没用，因为你不能在多项式的时间里去验证它。下面我要举的例子是一个经典的例子，它指出了一个目前还没有办法在多项式的时间里验证一个解的问题。很显然，前面所说的 Hamilton 回路是 NP 问题，因为验证一条路是否恰好经过了每一个顶点非常容易。但我要把问题换成这样：试问一个图中是否不存在 Hamilton 回路。这样问题就没法在多项式的时间里进行验证了，因为除非你试过所有的路，否则你不敢断定它“没有 Hamilton 回路”。

NPC 类问题

之所以要定义 NP 问题，是因为通常只有 NP 问题才可能找到多项式的算法。我们不会指望一个连多项式地验证一个解都不行的问题存在一个解决它的多项式级的算法。相信读者很快明白，信息学中的号称最困难的问题——“NP 问题”，实际上是在探讨 NP 问题与 P 类问题的关系。

很显然，所有的 P 类问题都是 NP 问题。也就是说，能多项式地解决一个问题，必然能多项式地验证一个问题的解——既然正解都出来了，验证任意给定的解也只需要比较一下就可以了。关键是，人们想知道，是否所有的 NP 问题都是 P 类问题。

我们可以再用集合的观点来说明。如果把所有 P 类问题归为一个集合 P 中，把所有 NP 问题划进另一个集合 NP 中，那么，显然有 P 属于 NP。现在，所有对 NP 问题的研究都集中在一个问题上，即究竟是否有 P = NP？通常所谓的“NP 问题”，其实就一句话：证明或推翻 P = NP。

约化与 NPC 问题的存在性

约化的概念

为了说明 NPC 问题，我们先引入一个概念——约化(Reducibility，有的资料上叫“归约”)。

简单地说，一个问题 A 可以约化为问题 B 的含义即是，可以用问题 B 的解法解决问题 A，或者说，问题 A 可以“变成”问题 B。

《算法导论》上举了这么一个例子。比如说，现在有两个问题：求解一个一元一次方程和求解一个一元二次方程。那么我们说，前者可以约化为后者，意即知道如何解一个一元二次方程那么一定能解出一元一次方程。我们可以写出两个程序分别对应两个问题，那么我们能找到一个“规则”，按照这个规则把解一元一次方程程序的输入数据变一下，用在解一元二次方程的程序上，两个程序总能得到一样的结果。这个规则即是：两个方程的对应项系数不变，一元二次方程的二次项系数为 0。按照这个规则把前一个问题转换成后一个问题，两个问题就等价了。

同样地，我们可以说，Hamilton 回路可以约化为 TSP 问题(Travelling Salesman Problem，旅行商问题)：在 Hamilton 回路问题中，两点相连即这两点距离为 0，两点不直接相连则令其距离为 1，于是问题转化为在 TSP 问题中，是否存在一条长为 0 的路径。Hamilton 回路存在当且仅当 TSP 问题中存在长为 0 的回路。

“问题 A 可约化为问题 B”有一个重要的直观意义：B 的时间复杂度高于或者等于 A 的时间复杂度。也就是说，问题 A 不比问题 B 难。这很容易理解。既然问题 A 能用问题 B 来解决，倘若 B 的时间复杂度比 A 的时间复杂度还低了，那 A 的算法就可以改进为 B 的算法，两者的时间复杂度还是相同。正如解一元二次方程比解一元一次方程难，因为解决前者的方法可以用来解决后者。

很显然，约化具有一项重要的性质：约化具有传递性。如果问题 A 可约化为问题 B，问题 B 可约化为问题 C，则问题 A 一定可约化为问题 C。这个道理非常简单，就不必阐述了。

现在再来说一下约化的标准概念就不难理解了：如果能找到这样一个变化法则，对任意一个程序 A 的输入，都能按这个法则变换成程序 B 的输入，使两程序的输出相同，那么我们说，问题 A 可约化为问题 B。

当然，我们所说的“可约化”是指的可“多项式地”约化(Polynomial - time Reducible)，即变换输入的方法是能在多项式的时间里完成的。约化的过程只有用多项式的时间完成才有意义。

NPC 问题的出现

从约化的定义中我们看到，一个问题约化为另一个问题，时间复杂度增加了，问题的应用范围也增大了。通过对某些问题的不断约化，我们能够不断寻找复杂度更高，但应用范围更广的算法来代替复杂度虽然低，但只能用于很小的一类问题的算法。

再回想前面讲的 P 和 NP 问题，联想起约化的传递性，自然地，我们会想问，如果不断地约化上去，不断找到能“通吃”若干小 NP 问题的一个稍复杂的大 NP 问题，那么最后是否有可能找到一个时间复杂度最高，并且能“通吃”所有的 NP 问题的这样一个超级 NP 问题？

答案居然是肯定的。也就是说，存在这样一个 NP 问题，所有的 NP 问题都可以约化成它。换句话说，只要解决了这个问题，那么所有的 NP 问题都解决了。

这种问题的存在难以置信，并且更加不可思议的是，这种问题不只一个，它有很多个，它是一类问题。这一类问题就是传说中的 NPC 问题，也就是 NP - 完全问题。NPC 问题的出现使整个 NP 问题的研究得到了飞跃式的发展。我们有理由相信，NPC 问题是最复杂的问题。

NPC 问题的定义与意义

NPC 问题的定义

NPC 问题的定义非常简单。同时满足下面两个条件的问题就是 NPC 问题。首先，它得是一个 NP 问题；然后，所有的 NP 问题都可以约化到它。证明一个问题是 NPC 问题也很简单。先证明它至少是一个 NP 问题，再证明其中一个已知的 NPC 问题能约化到它（由约化的传递性，则 NPC 问题定义的第二条也得以满足；至于第一个 NPC 问题是怎么来的，下文将介绍），这样就可以说它是 NPC 问题了。

NPC 问题的意义

既然所有的 NP 问题都能约化成 NPC 问题，那么只要任意一个 NPC 问题找到了一个多项式的算法，那么所有的 NP 问题都能用这个算法解决了，NP 也就等于 P 了。因此，给 NPC 找一个多项式算法太不可思议了。因此，前文才说，“正是 NPC 问题的存在，使人们相信 P ≠ NP”。我们可以就此直观地理解，NPC 问题目前没有多项式的有效算法，只能用指数级甚至阶乘级复杂度的搜索。

NP - Hard 问题与逻辑电路问题

NP - Hard 问题

顺便讲一下 NP - Hard 问题。NP - Hard 问题是这样一种问题，它满足 NPC 问题定义的第二条但不一定要满足第一条（就是说，NP - Hard 问题要比 NPC 问题的范围广）。NP - Hard 问题同样难以找到多项式的算法，但它不列入我们的研究范围，因为它不一定是 NP 问题。即使 NPC 问题发现了多项式级的算法，NP - Hard 问题有可能仍然无法得到多项式级的算法。事实上，由于 NP - Hard 放宽了限定条件，它将有可能比所有的 NPC 问题的时间复杂度更高从而更难以解决。

逻辑电路问题

不要以为 NPC 问题是一纸空谈。NPC 问题是存在的。确实有这么一个非常具体的问题属于 NPC 问题。下文即将介绍它。

下文即将介绍逻辑电路问题。这是第一个 NPC 问题。其它的 NPC 问题都是由这个问题约化而来的。因此，逻辑电路问题是 NPC 类问题的“鼻祖”。

逻辑电路问题是指的这样一个问题：给定一个逻辑电路，问是否存在一种输入使输出为 True。

什么叫做逻辑电路呢？一个逻辑电路由若干个输入，一个输出，若干“逻辑门”和密密麻麻的线组成。看下面一例，不需要解释你马上就明白了。

这是一个较简单的逻辑电路，当输入 1、输入 2、输入 3 分别为 True、True、False 或 False、True、False 时，输出为 True。

有输出无论如何都不可能为 True 的逻辑电路吗？有。下面就是一个简单的例子。

上面这个逻辑电路中，无论输入是什么，输出都是 False。我们就说，这个逻辑电路不存在使输出为 True 的一组输入。

回到上文，给定一个逻辑电路，问是否存在一种输入使输出为 True，这即逻辑电路问题。

逻辑电路问题属于 NPC 问题。这是有严格证明的。它显然属于 NP 问题，并且可以直接证明所有的 NP 问题都可以约化到它（不要以为 NP 问题有无穷多个将给证明造成不可逾越的困难）。证明过程相当复杂，其大概意思是说任意一个 NP 问题的输入和输出都可以转换成逻辑电路的输入和输出（想想计算机内部也不过是一些 0 和 1 的运算），因此对于一个 NP 问题来说，问题转化为了求出满足结果为 True 的一个输入（即一个可行解）。

NPC 问题的涌现与 P = NP 问题的现状

有了第一个 NPC 问题后，一大堆 NPC 问题就出现了，因为再证明一个新的 NPC 问题只需要将一个已知的 NPC 问题约化到它就行了。后来，Hamilton 回路成了 NPC 问题，TSP 问题也成了 NPC 问题。现在被证明是 NPC 问题的有很多，任何一个找到了多项式算法的话所有的 NP 问题都可以完美解决了。因此说，正是因为 NPC 问题的存在，P = NP 变得难以置信。

P = NP 问题还有许多有趣的东西，有待大家自己进一步的挖掘。攀登这个信息学的巅峰是我们这一代的终极目标。现在我们需要做的，至少是不要把概念弄混淆了。

Python 猫注：

以上文章写于 2006 年，巧合的是在我读到这篇文章的两个月前，原作者又更新了一篇《16 年后重谈 P 和 NP 问题》的文章。你已读到了这里，说明对此话题很感兴趣，为了方便大家阅读，我把新文也一并分享出来：
来源：http://www.matrix67.com/blog/archives/7084#more-7084
 
 
2006 年，我在博客（当时还是 MSN Space）上发了 《什么是 P 问题、NP 问题和 NPC 问题》 一文。这是我高二搞信息学竞赛时随手写的一些东西，是我的博客中最早的文章之一。今天偶然发现，这篇现在看了恨不得重写一遍的“科普”竟仍然有比较大的阅读量。时间过得很快。《星际争霸》（StarCraft）出了续作，德国队 7 比 1 大胜东道主巴西，《学徒》（The Apprentice）里的那个家伙当了总统，非典之后竟然出了更大的疫情。现在已经是 2022 年了。这 16 年的时间里，我读了大学，出了书，娶了老婆，养了娃。如果现在的我写一篇同样话题的科普文章，我会写成什么样呢？正好，我的新书《神机妙算：一本关于算法的闲书》中有一些相关的内容。我从书里的不同章节中摘选了一些片段，整理加工了一下，弄出了下面这篇文章，或许能回答刚才的问题吧。

P = NP 问题的进一步探讨

一个生活中的算法问题

有一天，我和老婆去超市大采购。和往常一样，结完账之后，我们需要小心谨慎地规划把东西放进购物袋的顺序，防止东西被压坏。这并不是一件容易的事情，尤其是考虑到各个物体自身的重量和它能承受的重量之间并无必然联系。鸡蛋、牛奶非常重，但同时也很怕压；毛巾、卫生纸都很轻，但却能承受很大的压力。

于是，我突然想到了这么一个问题：给定 $n$ 个物体各自的重量和它能承受的最大重量，判断出能否把它们叠成一摞，使得所有的物体都不会被压坏（一个物体不会被压坏的意思就是，它上面的物体的总重小于等于自己能承受的最大重量）。

事实证明，这是一个非常有趣的问题。这里，我们不妨给出一组数据供大家玩玩。

假设有 A、B、C、D 四个物体，其中：物体 A 的自重为 1，最大承重为 9；物体 B 的自重为 5，最大承重为 2；物体 C 的自重为 2，最大承重为 4；物体 D 的自重为 3，最大载重为 12。在这个例子中，安全的叠放方式是唯一的，你能找出来吗？

答案：C 在最上面，其次是 B，其次是 A，最下面是 D。注意，在这个最优方案中，最上面的物体既不是自身重量最小的，也不是承重极限最小的，而是自身重量与承重极限之和最小的。事实上，最优方案中的四个物体就是按照这个和的大小排列的！对于某种叠放方案中的某一个物体，不妨把它的最大载重减去实际载重的结果叫作它的安全系数。

我们可以证明，这种按自身重量与载重能力之和排序的叠放策略可以让最危险的物体尽可能安全，也就是让最小的那个安全系数达到最大。如果此时所有物体的安全系数都是非负数，那么我们就相当于有了一种满足要求的叠放方案；如果此时仍然存在负的安全系数，那么我们就永远找不到让所有物体都安全的叠放方案了。

假设在某种叠放方案中，有两个相邻的物体，上面那个物体的自身重量和最大载重分别为 $W_1$ 和 $P_1$，下面那个物体的自身重量和最大载重分别为 $W_2$ 和 $P_2$。再假设它俩之上的所有物体的重量之和是 $W$，这是这两个物体都要承担的重量。如果 $W_1+P_1$ 大于 $W_2+P_2$，那么把这两个物体的位置交换一下，会发生什么事情呢？原先下面那个物体的安全系数为 $P_2-W-W_1$，移到上面去之后安全系数变成了 $P_2-W$，这无疑使它更安全了。原先上面那个物体的安全系数为 $P_1-W$，移到下面后安全系数变成了 $P_1-W-W_2$，这个值虽然减小了，但却仍然大于原先另一个物体的安全系数 $P_2-W-W_1$（这里用到了 $W_1+P_1>W_2+P_2$ 的假设）。因此，交换两个物体之后，不但不会刷新安全系数的下限，相反有时还能向上改进它。

所以说，我们可以不断地把自身重量与载重能力之和更小的物体换到上面去，反正这不会让情况变得更糟。最终得到的最优方案，也就与我们前面给出的结论一致了。

算法与时间复杂度

为了解决某类问题，我们经常需要给出一个策略，或者说一个方案，或者说一个处理过程，或者说一系列操作规则，或者更贴切的，一套计算方法。这就是所谓的“算法”（algorithm）。

让我们来总结一下。我们的问题是：给定 $n$ 个物体各自的重量，以及每个物体最大可以承受的重量，判断出能否把它们叠成一摞，使得所有的物体都不会被压坏。它的算法则是：按照自身重量与最大承重之和进行排序，然后检验这是否能让所有物体都不被压坏，它的答案就决定了整个问题的答案。有了算法后，实际的计算过程一般就会交给计算机来完成的。程序员的工作，就是编写代码，把算法告诉计算机。

让计算机把每个物体的自身重量和最大承重加起来，这好办。如果有 $n$ 个物体，那就要算 $n$ 遍加法。给它们排序的时候，我们要依次做下面这些事情：

• 把 $n$ 个数逐一过一遍，找出最小的那个数（$n$ 次操作）
• 把最小的那个数放到第 1 个位置（1 次操作）
• 把剩下的 $n-1$ 个数逐一过一遍，找出最小的那个数（$n-1$ 次操作）
• 把最小的那个数放到第 2 个位置（1 次操作）
• ……

这要用 $n+1+(n-1)+1+\cdots +1+1=\frac{n^2+3n}{2}$ 次操作。物体从上到下该怎么摆，现在就知道了。为了检验有没有东西被压坏，则需要把物体的重量从上到下累加一遍，边加边要和下一个物体的承重做比较。考虑到最上面的物体不用做检验，操作次数姑且就算 $2(n-1)$ 吧。这样的话，整个算法需要 $\frac{n^2+9n}{2}-2$ 次操作。当然，在编写程序时，一些细节处可能还需要很多额外的操作。不过，对于运算速度极快的计算机来说，这都可以忽略不计。

计算机动辄处理成千上万的数据，多那么一两次操作不会从根本上影响整个处理过程的开销。为了评估处理数据的效率，我们更应该关注总操作次数的“级别”。我们甚至可以把 $\frac{n^2+3n}{2}$ 次操作、$\frac{n^2+9n}{2}-2$ 次操作以及 $2n^2+n+1$ 次操作、$10n^2-13n+500$ 次操作等等，统统都叫作“操作次数以 $n^2$ 的级别增长”，它们都代表着同一个意思：当 $n$ 很大的时候，如果 $n$ 变成了原来的 $k$ 倍，那么总的开销大致就会变成原来的 $k^2$ 倍。

1894 年，德国数学家保罗·巴赫曼（Paul Bachmann）提出了一种使用起来非常方便的“大 O 记号”（big O notation），用到这里真是再适合不过了。如果某个函数 $f(n)$ 的增长速度不超过 $n^2$ 的级别，那么我们就可以记下 $f(n)=O(n^2)$。因而，随着 $n$ 的增加，$\frac{n^2+3n}{2}$、$\frac{n^2+9n}{2}-2$、$2n^2+n+1$、$10n^2-13n+500$ 的增长速度都可以用 $O(n^2)$ 来表示。类似地，$\frac{n^3}{10}$、$\frac{n^3+3n}{2}$、$10n^3-6n^2+100$ 则都相当于 $O(n^3)$。

完成刚才那个算法需要的操作次数是 $O(n^2)$ 级别的。假设每次操作耗时相同，那么运行这个算法所需要的时间也应该是 $O(n^2)$ 级别的。更专业的说法则是，整个算法的“时间复杂度”（time complexity）为 $O(n^2)$。

1985 年由英特尔公司推出的 80386 芯片每秒钟可以执行 200 万个指令，1999 年的英特尔奔腾 III 处理器每秒钟可以执行 20 亿个指令，2012 年的英特尔酷睿 i7 处理器每秒则可以执行 1000 亿个以上的指令。

不妨假设，当 $n=10$ 的时候，借助上述算法，计算机只需要 0.1 毫秒就能得到答案。算法的时间复杂度为 $O(n^2)$，说明当 $n$ 增加到原来的 100 倍时，运行完成所需的时间会增加到原来的 10000 倍。因此，如果 $n$ 变成了 1000 时，计算机也只需要 1 秒就能得到答案。即使 $n$ 增加到了 100000，计算机也只需要 10000 秒就能得到答案，这大约相当于 2 个小时又 47 分钟。

其实，为了判断出这些物体能否安全叠放，我们似乎完全不必如此煞费心机。我们还有一个更基本的方法：枚举所有可能的叠放顺序，看看有没有满足要求的方案。$n$ 个物体一共会产生 $n!$ 种不同的叠放顺序，每次检验都需要耗费 $O(n)$ 的时间。所以，为了得到答案，最坏情况下的时间复杂度为 $O(n\cdot n!)$。

那么，我们为什么不采用这种粗暴豪爽的算法呢？主要原因大概就是，这种算法的时间复杂度有些太高。但是，既然计算机的运算速度如此之快，$O(n\cdot n!)$ 的时间复杂度想必也不在话下吧？让我们来看一看。仍然假设 $n=10$ 的时候，计算机只需要 0.1 毫秒就能得到答案。令人吃惊的是，若真的以 $O(n\cdot n!)$ 的级别增长，到了 $n=15$ 的时候，完成算法全过程需要的时间就已经增加到了 54 秒。当 $n=20$ 时，算法全过程耗时 1.34 亿秒，这相当于 1551 天，也就是 4.25 年。当 $n=30$ 时，算法全过程耗时 700 万亿年，而目前的资料显示，宇宙大爆炸也不过是在 137 亿年以前。如果 $n=100$ 的话，计算机需要不分昼夜地工作 $8.15\times 10^{140}$ 年才能得到答案。根据目前的宇宙学理论，到了那个时候，整个宇宙早已一片死寂。

多项式级增长与指数级增长

为什么 $O(n^2)$ 和 $O(n\cdot n!)$ 的差异那么大呢？原因就是，前者毕竟属于多项式级的增长，后者则已经超过了指数级的增长。

指数级的增长真的非常可怕，虽然 $n$ 较小的时候看上去似乎很平常，但它很快就会超出你的想象，完全处于失控状态。一张纸对折一次会变成 2 层，再对折一次会变成 4 层……如此下去，每对折一次这个数目便会翻一倍。因此，一张纸对折了 $n$ 次后，你就能得到 $2^n$ 层纸。当 $n=5$ 时，纸张层数 $2^n=32$；当 $n=10$ 时，纸张层数瞬间变成了 1024；当 $n=30$ 时，你面前将出现 $2^{30}=1073741824$ 层纸！一张纸的厚度大约是 0.1 毫米，这十亿多张纸叠加在一起，也就有 10 万多米。卡门线（Kármán line）位于海拔 100 千米处，是国际标准规定的外太空与地球大气层的界线。这表明，把一张纸对折 30 次以后，其总高度将会超出地球的大气层，直达外太空。

波斯史诗《王书》记载的故事也形象地道出了指数级增长的猛烈程度。一位智者发明了国际象棋，国王想要奖赏他，问他想要什么。智者说：“在这个棋盘的第一个格子里放上一颗大米，第二个格子里放上两颗大米，第三个格子里放上四颗大米，以此类推，每个格子里的大米数都是前一个格子的两倍。所有 64 个格子里的大米就是我想要的奖赏了。”国王觉得这很容易办到，便欣然同意了。殊不知，哪怕只看第 64 个格子里的大米，就已经有 $2^{63}\approx 9.22\times 10^{19}$ 颗了。如果把这些大米分给当时世界上的每个人，那么每一个人都会得到上千吨大米。国际象棋的棋盘里幸好只有 64 个格子。如果国际象棋的棋盘里有 300 个格子，里面的大米颗数就会超过全宇宙的原子总数了。

因而，在计算机算法领域，我们有一个最基本的假设：**所有实用的、快速的、高效的算法，其时间复杂度都应该是多项式级别的。**因此，在为计算机编写程序解决实际问题时，我们往往希望算法的时间复杂度是多项式级别的。

判定性问题与 P 问题

这里的“问题”一词太过宽泛，可能会带来很多麻烦，因而我们规定，接下来所说的问题都是指的“判定性问题”（decision problem），即那些给定某些数据之后，要求回答“是”或者“否”的问题。

在复杂度理论中，如果某个判定性问题可以用计算机在多项式级别的时间内解出，我们就说这个问题是一个 P 问题，或者说它属于集合 P。这里，P 是“多项式”的英文单词 polynomial 的第一个字母。之前那个叠放东西的问题，就是一个 P 问题。

历史上至少有过两个问题，它们看起来非常困难，非常不像 P 问题，但在人们的不懈努力之下，最终还是成功地加入了 P 问题的大家庭。其中一个是线性规划（linear programming），它是一种起源于二战时期的运筹学模型。1947 年，乔治·丹齐格（George Dantzig）提出了一种非常漂亮的算法叫作“单纯形法”（simplex algorithm），它在随机数据中的表现极为不错，但在最坏情况下却需要耗费指数级的时间。因此，很长一段时间，人们都在怀疑，线性规划是否有多项式级的算法。直到 1979 年，人们才迎来了线性规划的第一个多项式级的算法，它是由前苏联数学家列昂尼德·哈奇扬（Leonid Khachiyan）提出的。

另外一个问题则是质数判定问题（primality test）：判断一个正整数是否是质数（prime），或者说判断一个正整数是不是无法分成两个更小的正整数之积。人们曾经提出过各种质数判定的多项式级算法，但它们要么是基于概率的，要么是基于某些假设的，要么是有一定适用范围的。2002 年，来自印度理工学院坎普尔分校的阿格拉瓦尔（M. Agrawal）、卡亚勒（N. Kayal）和萨克斯泰纳（N. Saxena）发表了一篇重要的论文《PRIMES is in P》，给出了第一个确定性的、时间复杂度为多项式级别的质数判定算法，质数判定问题便也归入了 P 问题的集合。

NP 问题与 P ≠ NP 的猜想

同时，我们也有很多游离于集合 P 之外的问题。互联网安全高度依赖于一种叫作 RSA 算法的加密体系，里面用到了非常犀利的一点：在整数世界里，合成与分解的难度是不对等的。任意选两个比较大的质数，比如 19394489 和 27687937。我们能够很容易计算出它俩相乘的结果，它等于 536993389579193；但是，如果反过来问你，536993389579193 可以分解成哪两个质数的乘积，这却非常难以迅速作答。把一个大整数分解成若干个质数之积，这就是著名的“整数分解问题”（integer factorization problem）。目前，人们还没有找到一种快速有效的整数分解算法。也就是说，目前人们还不知道整数分解问题是否属于 P。（这里我们指的也是整数分解问题的判定性版本，即给定一个正整数 $N$ 和一个小于 $N$ 的正整数 $M$，判断出 $N$ 是否能被某个不超过 $M$ 的数整除。）人们猜测，整数分解很可能不属于 P。这正是 RSA 算法目前足够安全的原因。

另一个著名的问题叫作“子集和问题”（subset sum problem）：给定一个整数集合 $S$ 以及一个大整数 $M$，判断出能否在 $S$ 里选出一些数，使得它们的和正好为 $M$？比方说，假设集合 $S$ 为

{38, 71, 45, 86, 68, 65, 82, 89, 84, 85, 91, 8}

并且大整数 $M=277$，那么你就需要判断出，能否在上面这一行数里选出若干个数，使得它们相加之后正好等于 277。为了解决这类问题，其中一种算法就是，枚举所有可能的选数方案，看看有没有满足要求的方案。如果我们用 $n$ 来表示集合里的元素个数，那么所有可能的选数方案就有 $O(2^n)$ 种，检验每一种方案都需要花费 $O(n)$ 的时间，因而整个算法的时间复杂度为 $O(n\cdot 2^n)$。虽然人们已经找到了时间复杂度更低的算法，但没有一种算法的时间复杂度是多项式级别的。人们猜测，子集和问题很可能也不属于 P。

美国计算机科学家杰克·埃德蒙兹（Jack Edmonds）在 1964 年的一篇讨论某个矩阵问题的论文中，也提到了类似于 P 问题的概念：“当然，给定一个矩阵后，考虑所有可能的染色方案，我们一定能碰上一个符合要求的剖分，但这种方法所需要的工作量大得惊人。我们要寻找一种算法，使得随着矩阵大小的增加，工作量仅仅是呈代数式地上涨……和大多数组合问题一样，找出一个有限的算法很容易，找出一个满足上述条件的，从而能在实际中运用的算法，就不那么容易了。”

接下来，埃德蒙兹模模糊糊地触碰到了一个新的概念：“给定一个矩阵，它的各列最少能被剖分成多少个独立集？我们试着找出一个好的刻画方式。至于什么叫作‘好的刻画’，我们则采用‘绝对主管原则’。一个好的刻画，应该能透露出矩阵的某些信息，使得某个主管能够在助手找到一个最小的剖分方案之后，轻易地验证出这确实是最小的剖分方案。有了一个好的刻画，并不意味着就有一个好的算法。助手很可能还是得拼死拼活，才能找到那个剖分方案。”

埃德蒙兹后面所说的，不是设计一种多项式级的算法来寻找答案，而是设计一种多项式级的算法来验证答案的正确性。对于很多问题，这件事情是很好办的。为了向人们展示出确实有可能让所有的物体都不被压坏，我们只需要给出一种满足要求的物体叠放顺序，并让计算机用 $O(n)$ 的时间验证它的确满足要求即可。为了向人们展示出集合中的某些数加起来能得出 277，我们只需要提供一种选数的方法，并让计算机用 $O(n)$ 的时间求和检验。

对于有些问题来说，如果答案是肯定的，我们可能并没有一种非常明显的高效方法来检验这一点。不过，很容易看出，找出一个多项式级的答案验核算法，再怎么也比找出一个多项式级的答案获取算法更容易。很多看上去非常困难的问题，都是先找到多项式级的答案验核算法，再找到多项式级的答案获取算法的。

一个经典的例子就是质数判定问题。如果某个数确实是一个质数，你怎样才能在多项式级的时间里证明这一点？1975 年，沃恩·普拉特（Vaughan Pratt）在《每个质数都有一份简短的证明书》（Every Prime Has a Succinct Certificate）一文中给出了一种这样的方法，无疑推动了质数判定算法的发展。

还有些问题是如此之难，以至于目前人们不但没有找到多项式级的答案获取算法，而且还不知道是否存在多项式级的答案验核算法。比如经典的“第 K 大子集问题”（Kth largest subset problem）：给定一个含有 $n$ 个整数的集合 $S$，一个大整数 $M$，以及一个不超过 $2^n$ 的整数 $K$，判断出是否存在至少 $K$ 个不同的子集，使得每个子集里的元素之和都不超过 $M$？如果答案是肯定的，一个很容易想到的验证方法便是，把所有满足要求的 $K$ 个子集都列出来，并交由计算机审核。只可惜，子集的数目是指数级的，因而审核工作也将会花费指数级的时间。人们猜测，第 K 大子集问题很可能没有多项式级别的检验方法。

在复杂度理论中，一个问题有没有高效的答案验核算法，也是一个非常重要的研究课题。对于一个判定性问题，如果存在一个多项式级的算法，使得每次遇到答案应为“是”的时候，我们都能向这个算法输入一段适当的“证据”，让算法运行完毕后就能确信答案确实为“是”，我们就说这个问题是一个 NP 问题，或者说它属于集合 NP。为了解释“NP 问题”这个名字的来由，我们不得不提到 NP 问题的另一个等价定义：可以在具备随机功能的机器上用多项式级的时间解决的问题。

如果允许计算机的指令发生冲突，比如指令集里面既有 “如果遇到情况 A，则执行操作 B”，又有 “如果遇到情况 A，则执行操作 C”，我们就认为这样的计算机具备了随机的功能。这种新型的计算机就叫作“非确定型”（nondeterministic）机器。机器一旦遇到了矛盾纠结之处，就随机选择一条指令执行。你可以把机器面对的每一次随机选择都想象成是一个通向各个平行世界的岔路口，因而整台机器可以同时试遍所有的分支，自动探寻所有的可能。如果你看过尼古拉斯·凯奇（Nicolas Cage）主演的电影《预见未来》（Next），你或许会对这一幕非常熟悉。只要在任意一个分支里机器回答了“是”，那么整台机器也就算作回答了“是”。

在如此强大的机器上，很多问题都不是问题了。为了判断出能否让所有的物体都不被压坏，我们只需要让机器每次都从剩余物体中随便选一个放，看看由此产生的 $n!$ 种放法里是否有哪种放法符合要求。为了判断出集合中是否有某些数加起来等于 277，我们只需要让机器随机决定每个数该选还是不选，最后看看有没有哪次选出来的数之和正好是 277。

事实上，在非确定型计算机上可以用多项式级的时间获取到答案的问题，正是那些在确定型计算机上可以用多项式级的时间验核答案的问题，原因很简单：如果一个问题可以在非确定型计算机上获解，找到解的那个分支沿途做出的选择就成了展示答案正确性的最有力证据；反之，如果我们能在确定型计算机上验核出答案确实为“是”，我们便可以在非确定型计算机上随机产生验核所需的证据，看看在所有可能的证据当中会不会出现一条真的能通过验核的证据。“非确定型”的英文单词是 nondeterministic，它的第一个字母是 N；“多项式”的英文单词是 polynomial，它的第一个字母是 P。NP 问题便如此得名。

容易想到，所有的 P 问题一定都是 NP 问题，但反过来就不好说了。例如，子集和问题是属于 NP 的。然而，之前我们就曾经讨论过，人们不但没有找到子集和问题的多项式级解法，而且也相信子集和问题恐怕根本就没有多项式级的解法。因而，子集和问题很可能属于这么一种类型的问题：它属于集合 NP，却不属于集合 P。

1971 年，史提芬·古克（Stephen Cook）发表了计算机科学领域最重要的论文之一——《定理证明过程的复杂性》（The Complexity of Theorem - Proving Procedures）。在这篇论文里，史提芬·古克提出了一个著名的问题：P 等于 NP 吗？

如果非要用一句最简单、最直观的话来描述这个问题，那就是：能高效地检验解的正确性，是否就意味着能高效地找出一个解？数十年来，无数的学者向这个问题发起了无数次进攻。根据格哈德·韦金格（Gerhard Woeginger）的统计，仅从 1996 年算起，就有 100 余人声称解决了这个问题，其中 55 人声称 P 是等于 NP 的，另外 45 人声称 P 是不等于 NP 的，还有若干人声称这个问题理论上不可能被解决。

但不出所料的是，所有这些“证明”都是错误的。目前为止，既没有人真正地证明了 P = NP，也没有人真正地证明了 P ≠ NP，也没有人真正地证明了这个问题的不可解性。这个问题毫无疑问地成为了计算机科学领域最大的未解之谜。

在 2000 年美国克雷数学研究所（Clay Mathematics Institute）公布的千禧年七大数学难题（Millennium Prize Problems）中，P 和 NP 问题排在了第一位。第一个解决该问题的人将会获得一百万美元的奖金。

科学家对 P = NP 问题的看法

让我们来看一下，科学家们都是怎么看 P 和 NP 问题的吧。英国数学家、生命游戏（Game of Life）的发明者约翰·康威（John Conway）认为，P 是不等于 NP 的，并且到了 21 世纪 30 年代就会有人证明这一点。他说道：“我觉得这本来不应该是什么难题，只是这个理论来得太迟，我们还没有弄出任何解决问题的工具。”

美国计算机科学家、1985 年图灵奖获得者理查德·卡普（Richard Karp）也认为，P 是不等于 NP 的。他说：“我认为传统的证明方法是远远不够的，解决这个问题需要一种绝对新奇的手段。直觉告诉我，这个问题最终会由一位不被传统思想束缚的年轻科学家解决掉。”

美国计算机科学家、《自动机理论、语言和计算导论》（Introduction to Automata Theory, Languages and Computation）的作者杰夫瑞·厄尔曼（Jeffrey Ullman）同样相信 P 不等于 NP。他说：“我认为这个问题和那些困扰人类上百年的数学难题有得一拼，比如四色定理（four color theorem）。所以我猜测，解决这个问题至少还要 100 年。我敢肯定，解决问题所需的工具至今仍未出现，甚至连这种工具的名字都还没有出现。但别忘了，那些最伟大的数学难题刚被提出来的 30 年里，所面对的也是这样的情况。”

你或许会注意到，大家似乎都倾向于认为 P ≠ NP。事实上，根据威廉·加萨奇（William Gasarch）的调查，超过八成的学者都认为 P ≠ NP。这至少有两个主要的原因。

首先，证明 P = NP 看上去比证明 P ≠ NP 更容易，但即使这样，目前仍然没有任何迹象表明 P = NP。为了证明 P = NP，我们只需要构造一种可以适用于一切 NP 问题的超级万能的多项式级求解算法。在那篇划时代的论文里，史提芬·古克证明了一个颇有些出人意料的结论，让 P = NP 的构造性证明看起来更加唾手可得。给你一堆正整数，问能否把它们分成总和相等的两堆，这个问题叫作“分区问题”（partition problem）。

容易看出，分区问题可以转化为子集和问题的一个特例，你只需要把子集和问题中的目标设定成所有数之和的一半即可。这说明，子集和问题是一个比分区问题更一般的“大问题”，它可以用来解决包括分区问题在内的很多“小问题”。史提芬·古克则证明了，在 NP 问题的集合里，存在至少一个最“大”的问题，它的表达能力如此之强，以至于一切 NP 问题都可以在多项式的时间里变成这个问题的一种特例。很容易想到，如果这样的“终极 NP 问题”有了多项式级的求解算法，所有的 NP 问题都将拥有多项式级的求解算法。这样的问题就叫作“NP 完全问题”（NP - complete problem）。在论文中，史提芬·古克构造出了一个具体的 NP 完全问题，它涉及到了很多计算机底层的逻辑运算，能蕴含所有的 NP 问题其实也不是非常奇怪的事。

后来，人们还找到了很多其他的 NP 完全问题。1972 年，理查德·卡普发表了《组合问题中的可归约性》（Reducibility among Combinatorial Problems）一文。这是复杂度理论当中又一篇里程碑式的论文，“P 问题”“NP 问题”“NP 完全问题”等术语就在这里诞生。

在这篇论文里，理查德·卡普列出了 21 个 NP 完全问题，其中不乏一些看起来很“正常”、很“自然”的问题，刚才提到的子集和问题就是其中之一。1979 年，迈克尔·加里（Michael Garey）和戴维·约翰逊（David Johnson）合作出版了第一本与 NP 完全问题理论相关的教材——《计算机和难解性：NP 完全性理论导引》（Computers and Intractability: A Guide to the Theory of NP - Completeness）。该书的附录中列出了超过 300 个 NP 完全问题，这一共用去了 100 页的篇幅，几乎占了整本书的三分之一。

如果这些 NP 完全问题当中的任何一个问题拥有了多项式级的求解算法，所有的 NP 问题都将自动地获得多项式级的求解算法，P 也就等于 NP 了。然而，这么多年过去了，没有任何人找到任何一个 NP 完全问题的任何一种多项式解法。这让人们不得不转而相信，P 是不等于 NP 的。

人们相信 P ≠ NP 的另一个原因是，这个假设经受住了实践的考验。工业与生活中的诸多方面都依赖于 P ≠ NP 的假设。如果哪一天科学家们证明了 P = NP，寻找一个解和验证一个解变得同样容易，这个世界将会大不一样。1995 年，鲁塞尔·因帕利亚佐（Russell Impagliazzo）对此做了一番生动描述。

首先，各种各样的 NP 问题，尤其是那些最为困难的 NP 完全问题，都将全部获得多项式级的解法。工业上、管理上的几乎所有最优化问题都立即有了高效的求解方案。事实上，我们甚至不需要编程告诉计算机应该怎样求解问题，我们只需要编程告诉计算机我们想要什么样的解，编译器将会自动为我们做好一个高效的求解系统。

其次，很多人工智能问题也迎刃而解了。比方说，为了让计算机具备中文处理能力，我们可以准备一个训练集，里面包含一大批句子样本，每个句子都带有“符合语法”“不符合语法”这两种标记之一。接下来，我们要求计算机构造一个代码长度最短的程序，使得将这些语句输入这个程序后，程序能正确得出它们是否符合语法。显然，这个最优化问题本身是一个 NP 问题（这里有个前提，即这样的程序是存在的，并且是多项式级别的），因此计算机可以在多项式时间内找到这个最简程序。

根据奥卡姆剃刀原理（Occam’s razor），我们有理由相信，这个程序背后的算法也就是人类头脑中正在使用的算法，因此它能够适用于所给材料之外的其他语句，并具有自我学习的功能。数学家的很多工作也可以完全交给计算机来处理。寻找一个反例和验证一个反例变得同样简单，各种错误的猜想都将很快被推翻。事实上，寻找一个数学证明和验证一个证明的正确性也变得同样简单，因此各种正确的命题也能够很快找到一个最简的证明。

最后，不要高兴得太早——P = NP 的世界也将会是一个极不安全的世界。电子签名技术不再有效，因为伪造一段合法的签名变得和验证签名是否合法一样轻松。RSA 算法也不再有效，因为寻找一个质因数变得和判断整除性一样简单。事实上，发明任何新的密码算法都是徒劳——计算机可以根据一大批明文密文样本推算出生成密文的算法（只要这个算法本身是多项式的）。

更进一步，在网络上，你再也没法把人和人区别开来，甚至没法把人和计算机区别开来。计算机不仅能轻易通过图灵测试（Turing test），还能精确地模仿某一个特定的人。如果你能把某个人的网络聊天记录全部搜集起来，把这个人和网友们的对话全部递交给计算机，计算机将会很快学会如何模仿这个人。网络的身份鉴定必须要借助物理手段。即使是在科幻故事中，这样的设定也相当疯狂，可见 P = NP 有多不可能。

P = NP 问题的未来展望

虽然种种证据表明 P ≠ NP，但我们仍然无法排除 P = NP 的可能性。其实，如果 P 真的等于 NP，但时间复杂度的次数非常大非常大非常大，密码学的根基仍然不太可能动摇，我们的世界仍然不太可能大变。被誉为“算法分析之父”的计算机科学大师高德纳（Donald Knuth）还提出了这样一种可能：未来有人利用反证法证明了 P = NP，于是我们知道了所有 NP 问题都有多项式级的算法，但算法的时间复杂度究竟是多少，我们仍然一无所知！

对于很多人来说，找不到任何一个 NP 完全问题的多项式级算法，同样不应成为质疑 P = NP 的理由。荻原光德（Mitsunori Ogihara）认为，最终人们或许会成功地证明 P = NP，但这绝不是一两个人死死纠缠某一个 NP 完全问题就能办到的。对此，他做了更为细致的想象。

XX 世纪后期，一份非常简略的、从未发表过的草稿，无意中开辟了解决 P 和 NP 问题的道路。这份草稿出自 20 世纪的一位数学天才 FOO 之手，当时他正在尝试着建立某种代数结构的新理论。显然，FOO 很快放弃了这个想法，并且今后从未重新拾起这个课题。这份草稿一直卡在 FOO 的卧室地板的缝隙里，在后来的一次旧房翻新工程中才被工人们发现。由于草稿太过简略，因而当时并未引起太多关注。然而，几十年后，一群数学家发现，如果草稿上面的某个假设的某个变形成立，将会推出很多有意思的东西。虽然这不是 FOO 本来要做的假设，但它还是被人们称作“FOO 假设”，以纪念这位数学天才。
 
大约 100 年后，一群计算机科学家发现，如果 FOO 假设成立，那么某个特定的代数问题 Q 将会成为一个 NP 完全问题。几年后，计算机科学家们再次发现，如果（届时已经非常有名的）BAR 猜想成立，那么 Q 将会拥有多项式级的算法。把两者结合起来，于是得到：如果 FOO 和 BAR 都成立，那么 P = NP。
 
接下来的两个世纪里，这两个猜想都有了相当充分的研究。人们不断地得出各式各样的部分结果，剩余的特例则被转化为新的形式，直至每个猜想都被归为一句非常简明、非常具体的命题。最终，两组人马相继宣布，这两个命题都是正确的。第一组人马在 FOO 的诞辰前三周宣布，他们终于攻克了 BAR 猜想的最后一环。三个月后，第二组人马宣布，FOO 猜想正式得以解决。

未来究竟会发生什么？让我们拭目以待。

---

P/NP 问题 50 年：基础理论举步维艰，但 AI 正在不可能中寻找可能

原创 Lance Fortnow 返朴 2024年06月18日 08:01 北京

核心观点：

1. 至 2021 年，P/NP 问题已经 50 岁了，但其解决方案仍遥不可及。尽管算法与硬件的卓越进步使我们可以解决许多 NP 完全问题，但在密码系统的破解方面仍进展甚微。
2. 随着我们持续地在机器学习以及以数据为中心的计算领域取得激动人心的进步，P/NP 问题向我们提供了一个宝贵的视角，去了解在未来的机器学习领域什么是可能的，什么是不可能的。
3. 虽然 P/NP 问题一开始涉及复杂问题的计算求解，但如今我们将其视为绘制这个领域未来发展蓝图的一种方法。

（编者注：正文内参考文献序号为原文标注；原文发表于 2022 年。）

撰文 | Lance Fortnow（伊利诺斯理工学院计算机学院教授）

翻译 |许钊箐

1971 年 5 月 4 日，数学家、计算机科学家史蒂夫・库克（Steve Cook）在他的论文《定理证明过程的复杂性》（The Complexity of Theorem Proving Procedures）中向世人介绍了 P/NP 问题。如今，50 多年过去了，全世界仍在尝试解决这一问题。在 2009 年，我在《ACM 通讯》（Communications of the ACM）杂志上发表综述文章《P/NP 问题的现状》，探讨过这一话题**[13]**。

自 2009 年那篇文章发表以来，P/NP 问题及其相关的理论并没有显著的进展，但是计算领域无疑发生了巨变。云计算的发展促进了社交网络、智能手机、零工经济、金融科技、空间计算、在线教育等领域的进步，并且也许其中最重要的是数据科学与机器学习的崛起。在 2009 年，市值排名前十名的公司中仅仅只包含一家大型科技公司：微软。而截止至 2020 年 9 月，市值排名前七名的公司是：苹果（Apple）、微软（Microsoft）、亚马逊（Amazon）、谷歌（Alphabet）、阿里巴巴（Alibaba）、脸书（Facebook）、腾讯（Tencent）[38]。在此期间，美国计算机科学专业毕业生的数量增加了两倍多**[8]**，但仍远远不能满足岗位的需求。

在本文中，我选择通过 P/NP 问题的视角来看待计算、优化以及机器学习领域的进展，而不仅仅是简单修改或更新 2009 年文章的内容。我们将关注这些进展是如何使我们更接近 P=NP 的世界，P/NP 问题至今仍存在的局限性，以及已经涌现的新的研究机会。特别地，我会探讨我们是如何走向一个我称之为 “Optiland” 的世界，在那里我们几乎可以奇迹般地获得 P=NP 的许多优点，并且同时避免一些缺点，比如打破密码学的相关理论。

作为一个开放的数学难题，P/NP 问题至今是其中最重要的之一；它被列入克莱数学研究所的千禧年大奖难题之一**[21]**（该组织为其中每一个问题的求解提供 100 万美元的奖金）。在本文的最后，我也将陈述一些前沿计算机科学的相关理论结果。虽然这些结果没有让我们更接近于解决 P/NP 问题，但它们向我们展示了对于 P/NP 问题的思索仍然推动了该领域众多的重要研究。

P/NP 问题

是否存在 300 个 Facebook 用户彼此之间都是好友的关系？你将如何为这个问题提供一个解答？假设你在 Facebook 公司工作，可以访问公司所有数据，了解哪些用户是好友关系。你现在需要设计一个算法来寻找彼此都是好友并且人数足够多的朋友群体（Clique）。你可以先尝试搜索所有满足条件的 300 人朋友群体，但由于实际人数过多，无法全部搜索。你也可以选择一些更明智的方法，比如先尝试搜索一些小型朋友群体，之后再小的群体合并为更大的群体，但你会发现你所做的似乎都不起作用。事实上，没有人知道比遍历所有朋友群体明显更快的搜索方法，同时我们也不知道更快的方法是否不存在。

这基本上就是 P/NP 问题。NP 代表我们可以高效检验其解答的问题。如果我告知你有 300 人可能形成了一个满足条件的团体，你可以相对较快地检验他们彼此之间形成的 44850 对用户是否都是好友关系。上文的分团问题（Clique problem）便是一个 NP 问题。而 P 则表示我们可以高效地找到解的问题。对于分团问题，我们不知道它是否在 P 问题这个集合中。或许会令你惊讶的是，分团问题有一个被称为 NP 完备（NP-complete）的性质 —— 即当且仅当 P=NP 时，我们才可以高效地解决分团问题。许多其他问题也有这一性质，比如三着色问题（一副地图能否可以仅被三种颜色着色使得任意相邻的两个国家拥有不同的颜色？），旅行商问题（在众多的城市中找到一个最短路线，使得商人访问每座城市一次并回到初始的位置），以及其他成千上万的问题。

严格地来说，P 表示 “多项式时间”（polynomial time），对应一类求解时间是以输入长度为自变量的固定多项式的问题。而 NP 表示 “非确定性多项式时间”（nondeterministic polynomial time），对应一类非确定性图灵机可以不可思议地选择出最佳答案的问题。在本文中，读者可以把 P 和 NP 简单地看作可高效求解的问题以及可高效验证的问题。

如果读者希望对于 P/NP 问题的重要性有更深入的非专业讨论，可以阅读我 2009 年的综述文章**[13]或者我在 2013 年基于这篇综述文章写作的科普书籍[14]。对于更专业的介绍，由迈克尔・加里（Michael Garey）和大卫・约翰逊（David Johnson）[16]**在 1979 年创作的专著对于需要理解哪些问题是 NP 完备问题的读者非常合适。这本专著至今仍然是这方面的宝贵参考资料。

为什么我们现在谈论 P/NP 问题？

1971 年一个周二的下午，在美国俄亥俄州谢克海茨市的斯托弗萨默塞特酒店，史蒂芬・库克（Stephen Cook）在 ACM 计算理论专题研讨会上向与会者展示了他的论文，他证明了布尔表达式可满足性问题（Boolean Satisfiability Problem）是 NP 完备的，并且证明了重言式问题（Tautology）是 NP 困难（NP-hard）的**[10]**。这些定理也表明，重言式问题是一个不在 P 集合中不错的候选，并且我认为花费相当大的精力来尝试证明这个猜想是值得的。这样的证明将会是复杂性理论的重大突破。

与一个数学概念 “约会” 几乎总是一个挑战，历史上也许还有很多 P/NP 问题可能的诞生时间。算法和证明的基本概念可以被追溯到古希腊时期，但据我们所知，P/NP 这样一般性的问题他们从未考虑过。高效计算与非确定性的理论基础是在 20 世纪 60 年代发展起来的，而 P/NP 问题在此之前就形成了，只是我们不知道具体时间而已。

在 1956 年库尔特・哥德尔（Kurt Gödel）写给约翰・冯・诺伊曼（John von Neumann）的一封信中，哥德尔本质性地描述了 P/NP 问题。目前我们尚不清楚，当时身受癌症侵袭的冯・诺伊曼是否阅读了这封信。直到 1988 年，这封信才被人们发现，并广为传播。而 P/NP 问题是直到理查德・卡尔普（Richard Karp）1972 年发表论文**[23]指出大量著名组合问题（包括分团问题、三着色问题、以及旅行商问题）是 NP 完备的之后才真正成为一种现象。1973 年，当时在苏联的列昂尼德・莱文（Leonid Levin）在其 1971 年独立研究的基础上发表了一篇论文，其中定义了 P/NP 问题[27]**。而当莱文的论文传到西方的时候，P/NP 问题已经成为计算领域最重要的问题了。

乐观之地（Optiland）

在 1995 年的一篇经典论文中**[20]**，拉塞尔・因帕利亚佐（Russell Impagliazzo）描述了对于 P/NP 问题拥有不同程度可能性的五个世界：

1. 算法世界（Algorithmica）：P=NP 或者某种理论上的等价，比如 NP 问题的快速随机算法。
2. 启发世界（Heuristica）: 在最坏的情况下 NP 问题很难求解，但是通常情况下求解是容易的。
3. 悲观世界（Pessiland；译者注：引申自拉丁语悲观主义 pessimus）：我们可以轻易地构建难以求解的 NP 问题，但是很难构建我们知道解答的 NP 问题。这是所有可能性中最坏的，因为在这个世界中，我们既不能在通常情况下解决困难的问题，也不能由这些问题的难度获得任何明显的加密优势。
4. 单向加密世界（Minicrypt）：单向加密函数存在，但是我们没有公开密钥加密算法。
5. 加密狂欢世界（Cryptomania）: 公开密钥加密是可能的，也就是说，双方可以通过公开的信道交换加密信息。

这些对应不同情况的不同世界特意没有被正式定义。根据我们对于 P/NP 问题的了解，它们表明了未知的各种可能性。人们通常认为（不是全体统一地），我们生活在可以 “加密狂欢” 的世界里。

因帕利亚佐从 P/NP 的理论中总结出：“鱼与熊掌不可兼得（You can’t have it all）”。我们可以求解困难的 NP 问题，或者可以拥有密码学，两者必有其一，但不会共存。不过，或许我们正在前往一个现实中的 “乐观之地”（Optiland；译者注：与 pessiland 对应，引申自 Optimum）。机器学习和软件与硬件优化的进展，使我们能够对于此前长期被认为是困难或不可能的问题取得进展，比如语音识别与蛋白质折叠等问题，并且在大多数情况下我们的加密协议仍然是安全的。

在我 2009 年的综述文章**[13]**“如果 P=NP 会怎么样？” 章节里，我当时写道，“通过使用奥卡姆剃刀原则（Occam’s razor），学习变得容易了 —— 我们只需寻找与数据一致的最简单的方法”。近乎完美的视觉识别、语言理解、翻译，以及所有其他的学习任务都变得容易解决。我们也将更好地预测天气、地震以及其他自然现象。

如今，我们可以通过面部扫描来解锁智能手机，通过询问手机问题得到通常较为理想的回复，也可以将我们的问题翻译为另一种语言。智能手机会接收关于天气和极端气候的警报，而其预测能力比我们十几年前想象的要好得多。同时，除了小长度密钥加密会受到类似暴力破解的攻击之外，密码学理论基本没有被撼动。接下来，让我们来看一看计算、优化以及学习领域最近的进展是如何将我们领入 “乐观之地” 的。

困难问题的求解

2016 年，比尔・库克（Bill Cook, 与前文中的史蒂夫・库克没有关系）和他的同事们决定迎接这项挑战**[9]**：如何使用最短的路程到访英国的每一家酒吧？他们列出了 24727 家酒吧的名单，并确定了最后的酒吧旅行路线 —— 一次总长度 45495239 米的徒步旅行。这一距离比绕地球一圈还要长一些。

实际上，库克对该问题做了一些简化：他忽略了一些酒吧使得该问题有一个合适的规模。在一些英国媒体进行报道**[7]**之后，许多人抱怨名单中没有他们最爱的酒吧。因此库克团队重新整理了一份包含 49687 家酒吧的名单，而新的行程长度是 63739687 米（见下图）。与之前的路径相比，人们只需要多走 40% 的路程，便能到访数量是之前两倍多的酒吧。这个酒吧旅行的问题与旅行商问题（最著名的 NP 完备问题之一）是等价的。到访 49687 家酒吧所有可能路线的数量大约是 “3 后面跟着 211761 个 0”。当然库克的电脑不会遍历所有路线，他们使用了各种优化技术。更令人印象深刻的是，这份路线还附带一份基于线性规划对偶性的最优性证明。

穿过 49687 家英国酒吧的最短路线 图片来源：math.uwaterloo.ca/tsp/uk

库克团队也承担了一个更大的任务 —— 寻找一条穿越 200 多万恒星的最短路径，其中恒星之间的距离可以被计算。他们获得的路线总长度为 28884456 秒差距（译者注：1 秒差距约为 3.26 光年），和理论最佳值相比只有 683 秒差距的差别。

除了旅行商问题，我们在求解布尔可满足性问题和混合整数规划问题（Mixed-integer programming question）领域也取得了重大进展 —— 一种线性规划方法的变体，其中一些变量（不一定是全部）必须是整数。通过使用高度精炼的启发式方法、高速处理器、专业硬件以及分布式云计算，人们基本已经可以解决实践中出现的具有数以万计的变量和数十万甚至上百万的约束的问题。

面对需要求解的 NP 问题，人们通常会将问题转述为布尔可满足性问题或混合整数规划问题，进而使用最好的求解器求解。这些工具已经被成功地应用在电路与编码的验证与自动化测试、计算生物学、系统安全、产品与包装设计、金融交易中，甚至用于求解困难的数学问题。

数据科学与机器学习

如今，任何《ACM 通讯杂志》的读者和其他大多数人都不会忽视机器学习带来的变革性影响，尤其是通过神经网络实现的机器学习。使用人工神经元（笼统地讲，计算加权阈值函数）实现建模计算的概念可以追溯到 20 世纪 40 年代沃伦・麦卡洛克（Warren McCulloch）和沃尔特・皮茨（Walter Pitts）**[28]的研究。在 20 世纪 90 年代，约书亚・本希奥（Yoshua Bengio）、杰弗里・辛顿（Geoffrey Hinton）和杨立昆（Yann LeCun）[26]**提出了反向传播等算法，为多层神经网络学习训练的发展奠定了基础。更快、更广泛的分布式计算、专业硬件和海量数据也帮助并推动了机器学习的发展，使得它可以非常出色地完成众多原本需要人类完成的任务。计算机协会（the Association for Computing Machinery，ACM）也为本希奥、辛顿和立昆授予了 2018 年的图灵奖，以表彰他们的工作对人类社会产生的深远影响。

那么，机器学习与 P/NP 问题有什么联系？（在本节中，当我们提及 P=NP，它表示所有的 NP 问题在实践中都有相关的高效算法。）奥卡姆剃刀原则指出，“如无必要，勿增实体”，或者说，最简单的解释可能才是正确的。如果 P=NP，我们可以利用这一思想来建立一个强大的学习算法：找到一个与数据一致的最小的回路。但即便可能没有 P=NP 这个结论，机器学习也可以近似地实现这种方法，从而赋予了神经网络惊人的能力。然而，神经网络不太可能是那个 “最小的” 回路。如今使用深度学习技术训练的神经网络往往结构是固定的，其参数与网络中的权重有关。为了拥有足够的表达能力，人们通常需要设置数百万甚至更多的权重参数。而数量众多的参数限制了神经网络的能力：它们可以很好地进行面部识别，但是却无法根据示例来学习如何进行乘法运算。

通用分布（Universal distribution）和 GPT-3让我们考虑任意长度二进制字符串的分布。尽管均匀分布是明显不合理的，但是我们是否可以构建分布使得任意相同长度的字符串拥有相同的概率？实际上，有些字符串确实会比其他的更重要。比如，π 的前 100 万位数字比随机生成一个 100 万位数字更有意义。因此或许你会希望给更有意义的字符串设置更高的概率。实现这一目标的方法很多，而实际上存在一个接近于任何其他可计算分布的通用分布（读者可以参考科尔什赫等人的文章**[25]**）。通用分布与学习训练有很大的联系，例如，任意以小误差率学习这种分布的算法将可以学习所有可以计算的分布。可惜的是，即便 P=NP，通用分布也是不可计算的。不过，如果 P=NP，我们仍然可以得到一些有用的东西 —— 我们可以创建一个可高效计算的分布，使得它对于其他可高效计算的分布是通用的。

我们能从机器学习中获得什么？以 GPT（Generative Pre-trained Transformer，生成式预训练转换器）为例，特别是 2020 年发布的 GPT-3**[5]**。GPT-3 从尽可能多的书面语料库中提取了 4100 亿个标记，进而训练了 1750 亿个参数。它可以回答问题，可以根据提示书写文章，甚至可以生成代码。尽管它还有漫长的优化之路要走，但是它已经可以像人类一样创造内容，并因此受到好评。我们可以把 GPT-3 看作是一种分布，并考虑算法输出对应的概率 —— 即一个弱版本的通用分布。如果我们以一个给定的前缀限制通用分布，那么它就提供一个由该前缀提示的随机样本。GPT-3 也可以基于这样的提示，无需进一步训练就能处理极大范围的相关领域知识。随着这方面研究的进展，我们也将越来越接近一个通用度量标准并从中实现内置式学习：基于给定上下文生成一个随机的例子。

科学与医药在科学世界，我们已经通过大规模模拟取得了众多进展，比如探索核聚变反应。研究者们使用一种科学方法的范式：首先对于物理系统建立假设；然后使用模型进行预测；再用实验模拟检验该预测，而不是直接实现核聚变反应。如果测试结果与预期不同，再修改或推翻这个模型并重复以上的过程。

在我们拥有一个有说服力的模型之后，我们可以在现实反应堆中进行一些昂贵的实验测试。如果 P=NP，像上文提及的，我们可以使用奥卡姆剃刀理论来建立假说 —— 找到一个与数据一致的最小回路。机器学习的技巧可以紧接着沿着这个思路自动地创建假设。不管数据是来自于模拟、实验还是传感器，机器学习都可以创建出匹配数据的模型。然后我们可以使用这些模型来进行预测，并像前文提到过的那样检验做出的预测。

尽管机器学习可以帮助我们找到未发现的假设和模型，但所获得的结果未必是正确的。我们通常可以接受有 95% 置信水平的假设（这意味在 20 个不合格的假设中，有一个可能会被接受）。机器学习与数据科学的工具为我们生成假设的同时，也带来了结果不符合事实的风险。医学研究人员，特别是试图解决癌症等疾病的研究人员，常常遇到算法上的阻碍，因为生物系统极其复杂。我们知道 DNA 构成一种编码，它描述了我们的身体如何形成以及身体不同部分的功能，但我们对其运作原理知之甚少。

2020 年 11 月 30 日，谷歌的 DeepMind 公司发布了 AlphaFold—— 一种基于氨基酸序列预测蛋白质结构的新算法 [22]。AlphaFold 的预测准确度几乎达到了人工实验的水平，即通过实验构建氨基酸序列并测试其生成的蛋白质结构。虽然关于 DeepMind 是否真的 “解决” 了蛋白质折叠的问题仍存争议，并且现在便评估其影响力还为时过早，但从长远来看，它为我们提供了一个新的数字化工具来研究蛋白质，理解它们是如何相互作用，并学习如何设计蛋白质来对抗疾病。

P/NP 之外：象棋与围棋 NP 问题就像解谜游戏。数独问题就是 NP 完备的：在一个任意大小的宫格上，给定一些初始数字，然后求解其余空格中数字。但是对于两位玩家轮流执子的回合制游戏，比如象棋和围棋，如果我们想知道谁会在给定棋局下获胜，情况又会怎么样呢？事实上，即便是 P=NP，我们也未必可以找到完美的棋类算法。我们不得不考虑对于黑子的每一步，白子都可以走出合适的一步，并不断循环直到白棋胜利。而设计这种交替的算法仅仅依靠 P=NP 是不够的。这一类游戏的算法设计被称为 PSPACE-hard—— 在没有时间限制下，使用合理的存储容量进行计算是困难的。根据具体的规则设定，象棋和围棋的算法设计会更有难度。（感兴趣的读者可以阅读德迈纳与赫恩的文章 [11]。）

不过，这并不意味着在假设 P=NP 的前提下，我们不能找到一个好的棋类算法。你可能做出一个大小合适的高效计算机程序，使其优于所有比它体量略小的高效程序。另一方面，即便没有 P=NP 这一假设，计算机在棋类方面已经足够强大。在 1997 年，IBM 的超级电脑 “深蓝” 击败了当时的国际象棋世界冠军加里・卡斯帕罗夫（Gary Kasparov），然而在当时，即便是与有实力的业余选手的对决，围棋程序也难以取胜。在这之后，机器学习在计算机游戏的算法设计方面取得了巨大的进步。让我们直接跳过这段悠久的历史，来看看 2017 年 DeepMind 开发的 AlphaZero**[35]**。

AlphaZero 使用了一种被称为蒙特卡洛树搜索（MCTS）的技术 —— 让双方玩家随机地落子从而决定最佳的棋路方案。AlphaZero 使用深度学习来预测棋局的最佳分布，以优化使用 MCTS 获胜的机会。虽然 AlphaZero 并不是第一个使用 MCTS 的程序，但是它没有任何内置策略或者访问之前的棋类数据库 —— 它仅仅假设了游戏的规则。这也使得 AlphaZero 在国际象棋和围棋上都表现得出色，这两种游戏除了交替回合制和固定大小的棋盘之外截然不同。DeepMind 最近进一步地研究了 MuZero**[33]**—— 它甚至没有完整的规则，仅仅有一些棋盘位置的表示，一系列符合规则的落子，以及哪些情况是赢、输或者平局。现在我们已经明白，在国际象棋和围棋中，纯粹的机器学习可以很轻易地击败人类或者其他算法。而人为地干预只会妨碍它。对于象棋和围棋这类游戏，即便 P=NP 不足以解决这类问题，但机器学习却可以取得成功。

可解释的人工智能 很多机器学习算法似乎已经都运行得很好，但是我们却不理解为什么。如果你去观察为了语音识别而训练的神经网络，你通常会难以理解它为何做出这样的选择。我们为什么要关心这个问题呢？以下是一些原因：

1. 置信：我们如何知道神经网络运行正确？除了检查输入和输出，我们不会做其他任何的分析。不同的应用场景会有不同的置信水平：Netflix 推荐了一部水平不高的电影没什么关系，但如果是自动驾驶的汽车选择了一个错误的转弯，结果就很严重。
2. 公平：有很多例子表明，通过数据训练的算法受到了数据中有意或无意的偏差的影响。如果我们不理解程序，我们如何发现这些数据中的偏差？
3. 安全：如果使用机器学习来监管安全系统，我们将不知道哪些漏洞仍然存在，特别是当我们的敌手是不断变化的时候。但如果我们理解代码，我们就可以发现并修补安全漏洞。当然，如果敌手获得了代码，他们也可以发现漏洞。
4. 因果关系：目前我们最多只能检查机器学习算法是否与我们想要的输出类型相关。理解代码可以帮助我们理解数据中的因果关系，从而在科学与医学方面取得新的进步。

如果 P=NP，我们会得到一个更好的情况吗？如果我们有一个 NP 完全问题的快速算法，你可以将其用于匹配问题或旅行商问题，找到可能的最小回路，但你不会知道为什么这个回路是对的。另一方面，我们想要一个可解释算法的原因是我们希望可以理解它的性质，但如果 P=NP，我们可以直接导出这些性质。现在研究可解释的人工智能会议涌现出来，例如 ACM FAccT 会议。

机器学习的局限性虽然在过去十年中，机器学习已经展现了许多令人惊奇的结果，但很多系统还远未达到完美的水平，在大多数应用场景中，人类仍然更胜一筹。人们也将继续通过新的优化算法、数据收集与专业硬件来提高机器学习的能力。不过，机器学习似乎确实有其局限性。正如我们上文提到过的，机器学习让我们一定程度的接近 P=NP，但却永远无法替代 P=NP—— 机器学习在密码破解方面进展甚微，我们也将在本文后面看到这一点。

机器学习似乎无法学习简单的算术 —— 例如对大量的数字求和或者大数之间相乘。人们可以想到将机器学习与符号运算的数学工具结合起来。然而，尽管在定理证明方面我们取得了一些令人瞩目的进展 [19]，但这与我们期待中的实际科研任务仍距离遥远，即选取一篇科研文章，文中证明还未正式完成，使用 AI 系统补充细节并检验证明。

而 P=NP 将使这些任务变得简单，或者至少易于处理。机器学习在面对不属于其训练分布的任务时可能表现不佳。但这可能是概率较低的极端情况，例如训练数据中并未获得很好代表某个种族的人脸识别；或者可能是一种对抗性的尝试 —— 通过对输入进行微小的更改来强行获得不同的输出，比如把停车标志修改几个像素，从而让算法将其识别为一个限速标志**[12]**。深度神经网络算法可能有数百万个参数，因此它们在分布之外的泛化效果可能不理想。如果 P=NP，我们可以获得最小尺寸的模型从而有望实现更好的泛化，但如果没有相应的实验，我们永远也无法验证。

尽管机器学习令人印象深刻，但我们还没有获得任何接近于通用人工智能的东西 —— 这个术语指的是对于一个主题有真正的理解，或是实现真正的意识或自我认知的人工系统。定义这些术语可能是棘手的、有争议的，甚至是不可能的。于我个人而言，我从未见到过一个关于意识的正式定义，能够体现我对于意识的直观认识。我怀疑即使 P=NP，我们也永远无法实现强意义下的通用人工智能。

密码学

虽然我们在解决 NP 问题方面取得了很大进展，但是密码学的多种理论，包括单向函数（one-way functions）、安全散列算法（secure hashes）以及公钥密码学似乎都完好无损。如果 NP 问题存在一个高效的算法，那么除了那些在信息学上安全的密码系统，比如一次性密码簿和一些基于量子物理学的密码系统，其他所有密码系统都会被破解。我们已经见证了很多成功的网络安全攻击，但它们通常源于糟糕的代码漏洞、很弱的随机数生成器或者人为疏漏，很少是因为密码学理论的问题。

现在大多数 CPU 芯片都内置了 AES（Advanced Encryption Standard），因此一旦我们使用了公钥加密系统设置私钥，我们就可以像发送普通文本一样轻松地发送加密后的数据。加密技术为区块链和加密货币的发展提供了动力，这意味着人们对于加密技术的信任足以让他们愿意把货币换成比特。迈克尔・卡恩斯（Michael Kearns）和莱斯利・瓦利安特（Leslie Valiant）在 1994 年证明**[24]**，如果可以学习到最小的回路，甚至只是学到了最小的有界层的神经网络，那么它们就可以被用来分解质因数并破解公钥加密系统。而到目前为止，机器学习算法还从未成功破解过加密协议，不过也没有人期望机器学习算法可以成功。

为什么我们在许多其他 NP 问题取得了进展，而加密系统仍可以表现良好？在密码学中，我们可以选择问题，特别是可以将其设计成难以计算并可被广为测试的。而其他的 NP 问题通常来自应用问题或自然界。它们往往不是最困难的，也更容易折服于当下技术。

量子计算似乎威胁着当下保护我们互联网交易的公钥加密协议。秀尔算法（Shor’s algorithm）**[34]**可以进行质因数分解与其他数论计算。这种忧虑可以通过几种方式来缓和。尽管量子计算取得了一些令人印象深刻的进展，但要开发出能处理足够多纠缠比特的量子计算机，从而在一定规模上实现秀尔算法，我们可能仍需要几十年甚至几个世纪的时间。此外，研究者们也在开发可抵抗量子攻击的公钥密码系统并取得了一定的进展。更多量子计算内容我们将在后文详细讨论。

我们不知道因式分解问题是否是 NP 完备的，所以即便我们没有大规模的量子计算机，数学上的突破也有可能会带来高效的算法。但无论你对量子领域的未来有什么样的看法，如果拥有多种方法来优化公钥加密系统，它们可能都会派上用场。

如摩擦力般的复杂性

我们可以从计算复杂性中获得什么？此时，密码学可能会从你的脑海浮现。但或许就像存在摩擦力一样，宇宙使得某些计算很困难是有原因的。在物理世界中，克服摩擦力通常以消耗能量为代价，但是如果没有摩擦力，我们寸步难行。在计算世界中，错综复杂的计算一般会使计算过程缓慢而低效，但如果没有复杂性，就像没有摩擦力一样，我们也会有很多其他的问题。而 P=NP 在很多情况下，会让我们消除 “摩擦力”。

计算领域的最新进展表明，消除 “摩擦力” 有时会产生负面影响。例如人们不能直接阅读别人思想，只能看到其采取的行动。经济学家有一个术语，“偏好揭示”（preference revelation），旨在根据人们的行为来确定其偏好。在过去，由于缺乏数据与足够的算力，这一领域一直被认为最多只是非常不精确的一种艺术。

而如今，我们已经收集到了相当可观的数据 —— 来自人们的网络搜索、相片与视频、网购记录、虚拟与现实世界中的访问记录、社交媒体上的活动等等。而且，机器学习可以处理这些庞杂的信息，并对人们的行为做出异常精确的预测。如今，计算机比我们更了解我们自己。

我们甚至已经有足够的技术制作一副眼镜，戴上它就可以让我们了解对面人的名字、兴趣与爱好，甚至其政治立场。因此这种信息上的复杂性已不再赋予我们隐私。人们需要依赖法律和企业责任来保护隐私。

计算上的 “摩擦力” 不仅体现在隐私这一方面。在 1978 年，美国政府解除了对航空公司的定价管制，但如果想要找到一条航线的最佳价格，人们往往需要给多家航空公司打电话咨询，或者通过旅行社代理购票，当然旅行社也并不总是有动力去寻找最低的价格。因此航空公司致力于打造声誉，一些公司侧重优质的服务，另一些公司可以提供更低的价格。今天，我们可以很容易地找到最便宜的航班，因此航空公司在价格这个单一维度上投入了相当大的努力，他们通过计算优化定价并以牺牲飞行体验的代价来安排座位。

这种 “摩擦力” 在以前也有助于打击学生的作弊行为。在上世纪 80 年代，我读大学时必须计算作答的微积分问题，现在已经可以被 Mathematica 软件轻松解决。在我的入门理论课程中，我在为学生准备作业与考题的时候遇到了麻烦 —— 答案都可以在网上找到。随着 GPT-3 和其后续版本能力日益强大，甚至连论文与代码都可以自动生成，如果 GPT 这类的工具已经可以解决对于学生来说最复杂的问题，我们要如何激发学生？

股票交易过去是在现场进行的，交易员用手势来进行价格匹配。如今，交易算法自动地调整以适应新的价格，偶尔会导致价格瞬间暴跌。机器学习技术的发展已经引领了决策系统、人脸识别，将社交媒体内容与用户，还有司法判决进行大规模匹配。这些决策系统带来了一些好的改变，但也为我们带来了重大的挑战，比如放大偏见、加剧政治上的两极分化**[30]**。本文不详细探讨这个话题。

以上提到的这些只是许多可能的场景中的一小部分。作为计算机科学家，我们的目标是使计算尽可能的高效和简单，但我们也必须牢记减少 “摩擦力” 的代价。

量子计算机的能力

随着摩尔定律的极限越来越明显，计算机科学家们已经将目光投向非传统的计算模型以追寻下一阶段的突破。这促进了量子计算理论与应用的发展。大型科技公司，如谷歌、微软和 IBM，还有一大批初创公司，都已在量子计算机开发上投入了大量资源。美国已经启动了国家量子计划（National Quantum Initiative），其他国家，尤其是中国，也都加入了这一行列。

2019 年，谷歌**[1]宣布其使用了一台拥有 53 个量子比特的量子计算机实现了 “量子遥遥领先”，解决了当前传统计算无法解决的计算任务。尽管有些人质疑这一说法，但我们确实正处在量子计算新时代的边缘。然而我们还远没有达到实现皮特・秀尔（Peter Shor）算法[34]所需要的数万个量子比特的水平，从而解决当今计算机计算质因数分解问题。通常来说，量子计算被描述为由比特表示的状态数，比如 53 量子比特的机器有 253 个状态。这似乎表明，我们可以使用量子计算通过创建足够多的状态来解决 NP 完全问题 —— 例如，在一个图结构中，检验所有可能满足条件的团体。可惜的是，量子算法操控这些状态是受限的，而且所有的证据都表明，除了由格罗弗（Grover）算法[18]给出的二次加速改善，量子计算机无法解决 NP 完备问题[3]**。

复杂性的进展

自 2009 年我发表那篇综述文章之后，我们在理解高效计算能力方面取得了几项重大进步。虽然这些结果对于解决 P/NP 问题没有带来显著的进展，但依旧展现了它们是如何继续启发后续优秀研究的。

图同构： 一些 NP 问题可能既不是 P（高效可解），也不是 NP 完备的（像分团问题一样难）。其中我们前文提及的最著名的质因数分解问题，仍然需要指数级的时间来求解。而对于另一个类似的问题 —— 图同构问题，我们最近见证了激动人心的进展。图同构指的是在重新标号的意义下，两个图是否相同。以 Facebook 为例，给定两个千人的群组，我们能否将名字在两个群组中以一种方式相互对应，并保持人们之间的好友关系？

20 世纪 80 年代发表的与交互性证明相关的结果为证明图同构不是 NP 完备的提供了强有力的证据[4]。而且即便是简单的启发式算法通常也可以快速解决这类问题。可是我们仍然缺乏一个适用于所有情况的多项式时间的图同构算法。对于该问题，拉斯洛・巴拜（László Babai）在 2016 年取得了突破性成果[2]，他提出了一种图同构的拟多项式时间的算法。P 对应的问题的算法所用的是多项式时间，时间是 nk，其中 k 是常数，n 是输入数据的大小，如每一个群体的人数。而拟多项式时间的算法的运行时间是 $n^{klogn}$，与多项式时间相比要差一些，但与我们预料中 NP 完备问题求解所需的指数时间$2^{n^{Ɛ}}$相比已经有了巨大的进步。

巴拜的证明是一份将组合学与群论结合的杰出工作。尽管让算法在多项式时间内运行结束仍需要很多新的突破，但巴拜给出了一个重要的理论结果，是 P 与 NP 完备之间最重要问题之一的重大进展。

电路设计： 如果在完备的基（与门、或门、非门）下，小型电路不能求解 NP 问题，则 P≠NP。虽然上世纪 80 年代有很多关于电路复杂度的研究成果问世，但它们都没能接近于证明 P≠NP。2009 年的综述文章指出，在此前的 20 年里，电路复杂性领域没有取得新的重大成果。这种情况一直持续到 2010 年。1987 年，拉兹波洛夫（Razborov）**[32]和斯莫伦斯基（Smolensky）[36]**证明了对于固定素数 p 对应的常数深度电路 —— 由取余电路（Modp）、与门、或门、非门电路组成 —— 是不可能计算大多数函数的。不过，如果是有 6 对应的取余电路（Mod6），存在少量的一些证明工作。但即使是证明 NEXP（一种 NP 的指数时间版本）不能被常数深度的、由与或非门电路以及 6 对应的取余电路组成的小型电路计算这一问题，其仍在几十年中未被解决。因此常数深度的电路被认为在计算上能力很弱。在这方面工作的缺乏也反映了我们在阐释计算模型局限性这一领域取得的进展十分有限。

在 2010 年，瑞恩・威廉姆斯（Ryan Williams）**[39]证明了 NEXP 确实不能被常数深度、由 6 对应的取余电路或任意其他取余电路的小型电路计算求解。他构造了一种新技术，应用了可满足性算法。这种算法比尝试所有赋值并使用几种复杂工具来获得下界要好一些。后来，威廉姆斯和他的学生科迪・默里（Cody Murray）[29]**在此结果上更进一步，证明了即便是不确定的拟多项式时间的算法，也不存在对应的常数深度的、带有固定 m 对应的取余电路（Modm）的小型电路。然而证明不存在任意深度的小型电路可以求解 NP 问题（这正是证明 P≠NP 所需要的）仍然遥不可及。

复杂性的反击： 在 2009 年的综述文章中，有一节题为 “新希望”[13]。在这一节中，我们基于克坦・穆穆利（Ketan Mulmuley）和米林德・索霍尼（Milind Sohoni）提出的代数几何与表示理论，讨论了一种新的几何复杂性理论来攻破 P/NP 问题。简而言之，穆穆利和索霍尼试图构造高维多边形，以体现代数形式的 NP 问题的性质，并表明它具有任意与 P 问题的代数性质相对应多边形不同的性质。他们的猜想之一是认为多边形包含某种表示论的结构。然而在 2016 年，彼得・布尔吉瑟（Peter Bürgisser），克里斯蒂安・艾肯迈尔（Christian Ikenmeyer），和格蕾塔・帕诺娃（Greta Panova）**[6]**证明这种方法不会成功。

尽管布尔吉瑟、艾肯迈尔、与帕诺娃的工作否定了几何复杂性理论（GCT）区分 P 与 NP 问题的可能，人们仍然有可能根据表示论结构的数量构造不同的多边形。只不过我们不再应该期待 GCT 理论可以在不久的将来解决 P/NP 问题。

不可能的可能性

当我们思考 P/NP 问题时，我们发现它有许多不同的含义。P/NP 是正式定义的、长时间悬而未决、仍有百万美元悬赏的一个数学问题。在本文中，我们看到通过可计算性理论、电路设计、证明和代数几何等工具试图解决 P/NP 问题的努力。目前我们还没有一种强有力的方法解决 P/NP 问题。甚至从某种意义上说，我们到解决这个问题的距离比以前任何时候都要远。

还有一些 NP 问题是我们希望或需要解决的。在 1976 年的经典文献《计算机与难解性：一本 NP 完备性理论的指南》中**[16]**，加里（Garey）与约翰逊（Johnson）举了一个例子：一位倒霉的员工被要求解决一个 NP 完备的优化问题。最后这位员工找到老板说：“我找不到一个高效的算法，但这世界上的天才名流也一样找不到。“言外之意是老板不应该解雇这位员工，因为雇佣其他人也无法解决这个问题。

在 P/NP 问题的研究早期，我们将 NP 完备性看作一种障碍 —— 这些问题是我们无法解决的。但随着计算机与算法的发展，人们发现通过启发式算法、近似算法和暴力计算的结合，我们也可以在 NP 问题上取得进展。在加里和约翰逊的故事中，如果我是老板，我不会解雇这位员工，而是建议尝试使用混合整数规划、机器学习或者暴力搜索等方法。NP 完备意味着不可能的时代已经过去了。现在 NP 完备仅仅意味着可能没有一种算法可以永远有效和可扩展。

在我 2013 年关于 P/NP 问题的书中**[14]**，有一章名为 “美丽的世界”。在这一章中，我想象了一个理想化的世界：一位捷克数学家在这个世界中证明了 P=NP，从而得出一个对于所有的 NP 问题都非常高效的算法。尽管我们现在没有，也很可能永远不会生活在这样理想的世界，但是随着我们在计算上一步一步地前进，我们已经实现了很多医学进步，打造出与现实难以区分的虚拟世界，发明出创造新艺术作品的机器学习算法，P=NP 所带来的美妙或没那么美妙的结果似乎不再遥不可及。

我们正走在几乎完全颠覆 P/NP 问题的意义的道路上。与其将其认为是一种障碍，不如将 P/NP 问题看作一扇为我们指引方向，展现不可能中的可能性的大门。

致谢

感谢乔希・格罗乔（Josh Grochow）与我对 GCT 问题非常有帮助的讨论，以及库克允许我们使用相关图片。同样感谢乔希以及审稿人对于本文的建议与帮助。本文的一些材料改编自作者的博客。

参考文献

[1] Arute, F., Arya, K., Babbus, R., Bacon, D., Bardin, J.C., Barends, R., Biswas, R., Boxio, S., Brandao, F.G.S.L., Buell, D.A., et al. Quantum supremacy using a programmable superconducting processor. Nature 574, 7779 (2019), 505–510. https://doi.org/10.1038/s41586-019-1666-5

[2] Babai, L. Graph isomorphism in quasipolynomial time [extended abstract]. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (2016), 684–697. https://doi.org/10.1145/2897518.2897542

[3] Bennett, C., Bernstein, E., Brassard, G., and Vazirani, U. Strengths and weaknesses of quantum computing. SIAM J. Comput. 26, 5 (1997), 1510–1523.

[4] Boppana, R., Håstad, J., and Zachos, S. Does co-NP have short interactive proofs? Information Processing Letters 25, 2 (1987), 127–132.

[5] Brown, T.B., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D.M., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Suskever, I., and Amodei, D. Language models are few-shot learners (2020). arXiv:2005.14165 [cs.CL]

[6] Bürgisser, P., Ikenmeyer, C., and Panova, G. No occurrence obstructions in geometric complexity theory. J. of the American Mathematical Society 32, 1 (2019), 163–193. https://doi.org/10.1090/jams/908

[7] Coldwell, W. World’s longest pub crawl: Maths team plots route between 25,000 UK boozers. The Guardian (Oct. 21, 2016). https://www.theguardian.com/travel/2016/oct/21/worlds-longest-pub-crawlmaths-team-plots-route-between-every-pub-in-uk

[8] CRA Taulbee Survey. Computing Research Association (2020), https://cra.org/resources/taulbee-survey.

[9] Cook, B. Traveling salesman problem (2020), http://www.math.uwaterloo.ca/tsp/uk.

[10] Cook, S. The complexity of theorem-proving procedures. In Proceedings of the 3rd ACM Symposium on the Theory of Computing (1971), 151–158.

[11] Demaine, E.D. and Hearn, R.A. Playing games with algorithms: Algorithmic combinatorial game theory. Games of No Chance 3: Mathematical Sciences Research Institute Publications, Vol. 56. Michael H. Albert and Richard J. Nowakowski (Eds.), Cambridge University Press (2009), 3–56. http://erikdemaine.org/papers/AlgGameTheory_GONC3/

[12] Eykholt, K., Evtimov, I., Fernandes, E., Li, B., Rahmati, A., Xiao, C., Prakash, A., Kohno, T., and Song, D. Robust physical-world attacks on deep learning visual classification. In Proceedings of the IEEE Conf. on Computer Vision and Pattern Recognition (2018).

[13] Fortnow, L. The status of the P versus NP problem. Commun. ACM 52, 9 (Sept. 2009), 78–86. https://doi.org/10.1145/1562164.1562186

[14] Fortnow, L. The Golden Ticket: P, NP and the Search for the Impossible. Princeton University Press, Princeton, (2013). https://goldenticket.fortnow.com

[15] Fortnow, L and Gasarch, W. Computational Complexity. https://blog.computationalcomplexity.org

[16] Garey, M. and Johnson, D. Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York, (1979).

[17] Gödel, K. Letter to John von Neumann. (1956). https://www2.karlin.mff.cuni.cz/~krajicek/goedel-letter.pdf

[18] Grover, L. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th ACM Symposium on the Theory of Computing (1996), 212–219.

[19] Hartnett, K. Building the mathematical library of the future. Quanta Magazine (Oct. 1, 2020). https://www.quantamagazine.org/building-the-mathematical-library-of-the-future-20201001/.

[20] Impagliazzo, R. A personal view of average-case complexity theory. In Proceedings of the 10th Annual Conference on Structure in Complexity Theory. IEEE Computer Society Press (1995), 134–147. https://doi.org/10.1109/SCT.1995.514853

[21] Jaffe, A. The Millennium Grand Challenge in Mathematics. Notices of the AMS 53, 6 (June/July 2006), 652–660. http://www.ams.org/notices/200606/feajaffe.pdf

[22] Jumper, J., Evans, R., Pritzel, A., Green, T., Figurnov, M., Tunyasuvunakool, K., Ronneberger, O., Bates, R., Žídek, A., Bridgland, A., Meyer, C., Kohl, S.A.A., Potapenko, A., Ballard, A.J., Cowie, A., Romera-Paredes B., Nikolov, S., Jain, R., Adler, J., Back, T., Petersen, S., Reiman, D., Steinegger, M., Pacholska, M., Silver, D., Vinyals, O., Senior, A.W., Kavukcuoglu, K., Kohli, P., and Hassabis, D. High accuracy protein structure prediction using deep learning. In 14th Critical Assessment of Techniques for Protein Structure Prediction (Abstract Book) (2020), 22–24. https://predictioncenter.org/casp14/doc/CASP14_Abstracts.pdf

[23] Karp, R. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. Miller and J. Thatcher (Eds.). Plenum Press, New York, (1972), 85–103.

[24] Kearns, M. and Valiant, L. Cryptographic limitations on learning boolean formulae and finite automata. Journal of the ACM 41, 1 (Jan. 1994), 67–95. https://doi.org/10.1145/174644.174647

[25] Kirchherr, W., Li, M., and Vitányi, P. The miraculous universal distribution. The Mathematical Intelligencer 19, 4 (Sep. 1, 1997), 7–15. https://doi.org/10.1007/BF03024407

[26] LeCun, Y., Bengio, Y., and Hinton, G. Deep learning. Nature 521, 7553 (May 1, 2015), 436–444. https://doi.org/10.1038/nature14539

[27] Levin, L. Universal’ny̆ie pereborny̆ie zadachi (Universal search problems: in Russian). Problemy Peredachi Informatsii 9, 3 (1973), 265–266. Corrected English translation in.37

[28] McCulloch, W.S. and Pitts, W. A logical calculus of the ideas immanent in nervous activity. The Bulletin of Mathematical Biophysics 5, 4 (Dec. 1, 1943), 115–133. https://doi.org/10.1007/BF02478259

[29] Murray, C. and Williams, R. Circuit lower bounds for nondeterministic quasi polytime: An easy witness Lemma for NP and NQP. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (2018), 890–901. https://doi.org/10.1145/3188745.3188910

[30] O’Neil, C. Weapons of Math Destruction: How Big Data Increases Inequality and Threatens Democracy. Crown (2016), New York.

[31] Peikert, C. Lattice cryptography for the Internet. In Post-Quantum Cryptography, Michele Mosca (Ed.). Springer International Publishing, Cham (2014), 197–219.

[32] Razborov, A. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical Notes of the Academy of Sciences of the USSR 41, 4 (1987), 333–338.

[33] Schrittwieser, J., Antonoglou, I., Hubert, T., Simonyan, K., Laurent Sifre, L., Schmitt, S., Guez, A., Lockhart, E., Hassabis, D., Graepel, T., Lillicrap, T., and Silver, D. Mastering Atari, go, chess and shogi by planning with a learned model. Nature 588, 7839 (Dec. 1, 2020), 604–609. https://doi.org/10.1038/s41586-020-03051-4.

[34] Shor, P. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 5 (1997), 1484–1509.

[35] Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, L., Kumaran, D., Graepel, T., Lillicrap, T., Simonyan, K., and Hassabis, D. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science 362, 6419 (2018), 1140–1144. https://doi.org/10.1126/science.aar6404

[36] Smolensky, R. Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Proceedings of the 19th ACM Symposium on the Theory of Computing (1987), 77–82.

[37] Trakhtenbrot, R. A survey of Russian approaches to Perebor (brute-force search) algorithms. Annals of the History of Computing 6, 4 (1984), 384–400.

[38] Wikipedia contributors. List of public corporations by market capitalization. Wikipedia, the Free Encyclopedia. https://en.wikipedia.org/w/index.php?title=List_of_public_corporations_by_market_capitalization&oldid=1045945999.

[39] Williams, R. Nonuniform ACC circuit lower bounds. Journal of the ACM 61, 1, Article 2 (Jan. 2014). https://doi.org/10.1145/2559903.

本文经作者授权发表于《返朴》，原文译自 Fortnow, Lance. “Fifty years of P vs. NP and the possibility of the impossible.” Communications of the ACM 65.1 (2021): 76-85. DOI: 10.1145/3460351

---

via:

• 著名的 P=NP 问题到底是什么？Matrix67 Python猫 2022年08月05日 10:00 江苏
  https://mp.weixin.qq.com/s/5ky5QpH-2X9D1qWB5LgrMg
  • 什么是 P 问题、NP 问题和 NPC 问题？ 图灵人工智能 2023年06月10日 07:27 北京
    https://mp.weixin.qq.com/s/CBpVCbxi8Qr3BdfzW_8ftA
• P/NP 问题 50 年：基础理论举步维艰，但 AI 正在不可能中寻找可能 原创 Lance Fortnow 返朴 2024年06月18日 08:01 北京
  https://mp.weixin.qq.com/s/GMvRb9pI1gFGYWEG5xcxyw