一个价值百万美金的问题

前三期我们用三个大定律从不同方面讨论了计算机的极限。和之前的三期不同，这一期我们将从一个还没有被证明的问题入手，从复杂度的角度理解计算机领域中程序算法的极限。

2000年5月24日，在参考了一个世纪前希尔伯特提出的23个问题的做法之后，克雷数学研究所发布了七道千禧年大奖难题，总价值七百万美金。解答任何一道问题的第一个人将被授予一百万美金的奖励。在这七个问题中，一道关于解决P和NP的复杂度问题成为了整个计算机领域的焦点，因为这个问题的结论会直接给计算机领域带来截然不同的理论极限和发展前景。

在说明这个问题以及该问题在计算机领域的影响之前，我们先简单的阐述一下关于时间复杂度的定义以及复杂度学说中的几个大的问题集合。

首先需要说明的是，时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。比如说，如果一个程序在输入数据的规模变大到数百倍后，程序运行时间是不变的，那我们说这个程序的时间复杂度是O(1)，或常数级复杂度。比如在队列中插入或删除。无论队列多长，所需插入和删除的时间并不会因其发生改变。

同样，如果程序运行时间随着数据规模增大而等量增大，那我们称这个程序的时间复杂度为O(n)。比如在n个数中找最大值的算法。程序需要在遍历所有数值之后得到最大值。输入数据的规模n增大，所需要遍历的时间也等量增大。再比如像冒泡排序（bubble sort）这样数据扩大2倍，执行时间延长4倍的程序，我们称其复杂度为O(n²)。（冒泡排序是一种简单的排序算法，通过一次走访并比较数列中的两个元素，然后重复走访需要排序的数列来达到排序的效果。）

而像一些穷举法更有像O(a^n)甚至O(n!)这样的阶乘级复杂度，其中a为常数。在此基础上，复杂度被分成了两大类。第一种是像O(1), O(n), O(n^a)等，我们称其为多项式级的复杂度。而像O(a^n), 和O(n!)等，我们称其为非多项式级的复杂度。非多项式级的复杂度远远超过了多项式级，特别是在数据规模非常大的时候，其复杂度是计算机远无法承受的。在这里需要声明的是多项式级的复杂度并不代表简单，O(n^100)的复杂度也属于多项式级，但即便是n=100的输入数据也是一个很大的复杂度。

那么是否所有问题都能找到一个复杂度为多项式级的算法呢？答案是否定的。有些问题现在还不能用一个正确的算法来描述，或者说根本不可能用一个正确的算法来描述。比如之前提到的停机问题。图灵巧妙地用自洽的角度证明了停机问题的不可解，从而使得用算法来描述该类问题变得不可能。（具体参见《一个无法证明的逻辑问题》）。于是，所有问题因其不同的复杂度被分成了不同的集合。

首先是P类（Polynomial） 问题。如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。其次是NP类（None-deterministic Polynomial）问题。需要注意的是，NP类问题并不是P类问题的对立面（或非P类问题），而是指可以在多项式的时间里验证（而非获得）一个解的问题。换句话说，这类问题需要解题的人先猜一个答案，这个答案能在多项式时间里得到验证。这类问题通常解决起来很困难但验证起来很简单。比如判断在起点到终点的各种路径中是否有一条总路程小于10个单位长度的路径。解决这种问题最坏的可能需要穷举所有的路径，属于非多项式级的复杂度。而验证一个答案却很简单。只需要花O(n)的时间把我猜出来的路径长度加起来即可。这类问题就是NP问题。

我们按照常识判断，一个属于P类的问题，也一定属于NP类。这个很容易理解，能在多项式时间里找到答案就一定能在多项式时间里验证这个答案（大不了重做一次）。换句话说，P集合属于NP集合。那么问题来了，一个属于NP类的问题，是否也属于P类呢？换句话说，是否存在一个算法，能在多项式时间里找出NP类问题的解。也就是说，我们能否证明或者推翻P=NP？先别急着回答，因为它值一百万美金。

虽然P=NP这个结论到现在还没有得到证明或者被推翻，大多数研究者们普遍相信它是不成立的。2001年一项针对100名数学和计算机科学家的调查结果是其中61人相信P≠NP，2012年调查者重复了这一问卷，结果相信P≠NP的人增加到了84%。在研究方面，迄今为止最大的成果是史蒂芬库克在上世纪70年代时的成果。他定义了一个新的问题集合，使得所有NP问题都能规约成为这类问题。也就是说如果我们能找到一个拥有多项式级复杂度的算法来解答这个新集合里的任意一个问题，那么所有的NP问题就都是在多项式时间内可解的。这个新的集合被称作NP-完全（NP-Complete，简称NPC）问题。

为了进一步了解NPC问题，我们先来说一下规约。如果用解决问题B的办法能够也能够解决问题A，那么我们就说问题A可以被规约到问题B，尽管可能用解决问题B的方法解决问题A可能会增加不必要的复杂度。举个例子，尽管没有人会用解一元二次方程的通用公式来解一元一次方程，但至少我们也是能够用这个公式来解一元一次方程。所以我们就可以将一元一次方程的问题规约到一元二次方程问题上。就这样以此类推的规约下去，所有的NP问题都可以规约到一些更宽泛的问题里，而这些更宽泛的问题的集合就是NPC问题。由此，对P是否等价NP这一问题被简化成了证明是否能用有多项式级复杂度的算法来解决NPC问题。而史蒂芬库克也因其在该领域的贡献被授予了图灵奖。

随着计算机的普及，各个领域也开始使用计算机来做一些需要大量计算的研究。而多数这类研究最后都被证明是NPC问题。例如生物方面的基因序列比对[1]，经济方面的纳什均衡计算[2]，甚至是计算机领域本身的电路优化及核对[3]。所以对于P=NP这一问题的证明或推翻，大大的影响着各行各业的发展。

如果今后被证明了P=NP，那么在信息学上面密码的破解将变得容易，因为我们总能在多项式时间里找出正确密码。（正如之前提到的，多项式级的复杂度并不代表简单，即便是我们能证明P=NP也并不代表我们能找到一个相对复杂度较低的算法来破解密码。所以对那些觉得证明了P=NP之后密码将会形同虚设的说法，笔者还是抱持怀疑态度。）同时人工智能的发展前景也会一片大好，因为机器学习的过程也总能在多项式时间内完成。我们也能设计出更加优化的芯片使得计算机的极限被大大拓展。

相反，如果证明出P≠NP这一结论，那么传统计算机能做到的东西（包括机器学习）就会相对变得有限很多。不仅如此，上期提到的程序可并行化的程度也将因此受到影响。要了解这个问题，我们需要了解另外一个概念—NC规约。

NC规约（Niche Class) 是将P类问题规约到一个更小的PC类（P-Complete)[4]，使得这类问题能够在具有多项式复杂度的集成电路上运行，换句话说，就是该类问题能被有效并行化。如同P类问题属于NP类，NC类的问题也属于P类。但同样的问题是，我们无法证明是否P类问题也属于NC类，也就是说，我们在无法证明P=NC的情况下，无法知道现下可有效执行的算法（P类问题）是否都能被有效并行化。所以相信P≠NP这一结论的人同样也相信P≠NC这一结论。也就是说，大多数人也相信PC类的问题是无法被有效并行化的。除非今后真的有人证明出了P=NP这一结论，不然程序可并行化的上限也会被程序本身的复杂度所限制。

计算机今后发展的大方向在很大程度上将会受到复杂度理论的影响。在P和NP的关系还没有结论的今天，计算机科学家们也在按照自己所相信的结论在不同领域开展着计算机的研究。相信在不久的将来我们能看到有人为这个问题盖棺定论，为计算机的发展指明一条方向。毕竟在从克雷数学研究提出的千禧年大奖题到如今的不到20年的时间里，已经有一个叫格里戈里·佩雷尔曼的俄罗斯数学家因解决了庞加莱猜想而有资格拿走其中的100万美金了。只是他拒绝了接受这一百万美金的奖励。当然，这都是后话。

参考文献：

[1]  Gus eld, D. “Algorithms on Strings, Trees and Sequences,” Computer Science and Computational Biology. Cambridge University Press, 1997.

[2] Conitzer, V. and sandholm, T. “New Complexity Results about Nash Equilibria,” Games and Economic Behaviour 63, 2 (july 2008), 621–641.

[3] Fortnow, L. The status of the P versus NP problem. Commun. ACM 52, 78–86 (2009)

[4] Markov, I. L. Know your limits: a review of ‘limits to parallel computation: P-completeness theory’. IEEE Design Test 30, 78–83 (2013).

欢迎关注《走进计算机文化史》的系列文章：