真正的百万答题——七大千年数学难题之“NP问题”

2000年5月24日，美国克雷数学研究所，发布了新世纪最重要的七大数学难题。并为每个问题的解决悬赏一百万美元，答题时间没有限制。与1900年初的希尔伯特之23问遥相呼应。

千禧年七大问题分别是：

P对NP问题， 霍奇猜想， 黎曼假设，杨－米尔斯理论存在性与质量缺口，纳维-斯托克斯方程存在性与光滑性，BSD猜想。

这里面只有NP问题是计算机界的重大问题，而且排名榜首，足见其在当今数学界重要地位！

要了解NP问题，我们首先要去理解一个概念：时间复杂度。

城市位置分布（出发地 合肥）

假如我要在假期从合肥开始自驾游，计划游览完周边，上海，南京，武汉，三个城市，然后再回到合肥来，为了节约时间，我肯定是倾向于总里程最少的线路。那么我肯定要事先做好规划，于是我把所有可能的方案全部都列出来：

4座城市之间距离

这里总共有6种方案。

路线方案及里程

然后分别计算这些方案的总里程（不考虑实际道路情况）：

我们发现第 4种方案里程最短，于是我们选择这个方案。

如果我的假期足够长，不仅仅游览周围3个城市，打算游遍华中10个城市呢？这种情况下，我该怎样规划最优的游览路线。用最笨的办法，我们还是需要把所有可能的线路方案都列举出来，于是以此类推，就有10！种方案，大约3628800种方案。到这里，我们很快就发现，只要城市数目稍微大一点，采用穷举的方法就变得几乎不可行。因为，只要我们增加到第N个城市，可能的方案数目就会是原来方案数的N倍。所有我们能够使用枚举的N值实在是很小，稍大一点，计算量就会远远超过我们可以承受的水平。

指数爆炸的典型事件——麦粒和棋盘的故事

大家还记得那个在象棋盘上扔麦子的故事么？第一格放1粒麦子，第2格放2粒，。。。后面的麦子数目都是前一格的2倍，直到放满64格为止。事实上，这个游戏如果真的做到最后，那么从地球上的第一颗麦粒，一直到现在所种出的麦子都不够填上去。因为由于前后倍数的关系，数量很快就会急剧增大，人们给这样极具增加的过程起了一个形象的名字，叫指数爆炸。而我们前面说的那个自驾游的增加速度远比这个指数爆炸还要恐怖地多。所以为了衡量计算过程的复杂特性，我们引入了时间复杂度这个概念。这里不是指的是计算需要的世界，而是说，随着计算对象的增加，需要增加的计算量。

我们用这个O这个符号来记时间复杂度。棋盘麦粒问题的时间复杂度就是O(2ⁿ),前面的自驾游事件的复杂度就是O(n!)。这两种事件的考虑对象一旦超过了某个限度，计算的次数都是任何机器都难以承受的。

各种时间复杂度对比

那么有没有平稳推进的计算事件呢？也就是O在对象增加的情况下，计算次数比较平稳增加，没有出现类似的爆炸事件。当然有啊，比如，我们去计算一个M位的加法。我们把这个问题扔给计算机，计算机先转换成二进制之后，就开始逐位计算，完毕之后再以十进制的方式反馈给我们。模拟计算机处理过程，我们发现，M增加时，计算次数也仅增加M次，柔顺递增，于是加法的复杂度就是O(n)。乘法呢？要稍微多一点，根据加法与乘法的递进关系，我们可以得到乘法的复杂度为O(n²).至于除法，以及开方，立方等等运算，我们也可以很容易就归纳出复杂度大致的范围。事实上这一类计算的复杂度为O(关于n的多项式)，有的计算问题里包含了许多种基本运算，那么复杂度就高点，有的计算简单纯粹，那么复杂度就低些。人们归纳得出来，有一大类问题的复杂度总是n的一个多项式表达式。换句话说，这一类问题总可以在多项式时间内被求解出来。而我们目前的计算机能够处理的都是这样的一类计算。

加减乘除的计算都在多项式时间内

到这里，我们来到NP问题的第一步。上面说的总有一大类问题计算的时间复杂度是n的一个多项式，我们就把此类事件叫作P(Polynomial)问题。

千禧年七大数学难题之首——NP问题

然而，这个世界上存在着很多不一定就可以在多项式内被解决的问题。事实上，我们根本没办法去确定计算这些问题到底需要多少时间。假如，需要对一个有个长达1亿位的大数进行因子分解，用现在的任何计算机都是徒劳无用的，可能算是宇宙毁灭也不会有结果。也有可能你的计算机很聪明，它并不是按部就班去计算每一个可能会是因子的素数，它随机的从一堆可能的结果里找出一个数，找出一个我就验证一个，如果不是，我就再找下一个。最终在我们可以列举的多项式时间里成功分解了这个超级大数。这样一台并不按部就班的计算机就不是我们平时使用的那种你输入什么指令它就只能干什么的傻瓜机器了。于是，我们给这样的计算机起个新奇的名字，叫非确定性计算机。就是你不知道它会用什么方式来计算，但是它总会在有限的多项式时间内给你想要的结果。凡是符合这种情况的问题，我们就把这类问题叫作NP(Non-Deterministic Polynomial)问题。

非确定性计算机

好了，现在我们已经介绍理论这个千年难题中的两个概念了。我们要验证的问题就是NP问题有没有可能和P问题是同一类。也就是说，是否存在一种非常牛逼的算法，可以把NP的问题转化到使用确定计算机在多项式时间内得到结果。

我们的直觉上感觉，NP类问题的复杂度应该是介于多项式时间和指数型时间之间。人们迫不及待地研究了三十多年，没有一个人提过出一个否定或者肯定的证明。提出的都是这个猜想的猜想。

数学家们早已证明，对一个大数的分解就是NP问题。一个大数的素性检验工作，一不小心就会超过我们当今最厉害的超级计算机的运算能力。然而，如果给了你几个数字，让你去验证是否是这个超级大数的因子却是如此简单。

为我们的信息安全保驾护航的RSA算法

前面说到，RSA加密系统为什么在当今世界如此可靠，就是基于大数分解的困难性。我们现在假设一种可怕的情形，未来的人类证明了NP=P，这就说明存在一种方法使RSA的加密算法可以在多项式时间内被一台确定性计算机攻破。如果事实如此，那么我们肯定会去想方设法找寻这种旷世算法，可能这个旷世算法人类要寻找很多很多年。但是由于我们在理论上证明了的确存在这样的算法，那么找出来就是迟早的事情。若以后的人们真的证明了这个问题，那么从宣布证明的那一刻开始，RSA算法立马就会走下神坛，整个互联网交易的安全性就成为无稽之谈,人们会彻头彻尾地再设计一套全新的算法来取代RSA,因为理论上真有这样一种捷径可以破解它。假如未来的人类证明了NP≠P，RSA算法则仍然可以为人类牢固地服务很多年，直到新的更加安全的加密算法的出现。

NP问题的提出者——斯蒂芬·库克

1971年5月4日，斯蒂芬·库克证明了一个非常有前景的结论：

存在一个特殊的NP问题，如果这个NP问题可以在多项式时间内求解，那么其他任何的NP问题都可以在多项式问题内求到解。

这个问题也叫NP完全问题(也叫NPC问题)，这个问题对于人类巨大的诱惑性在哪儿呢？就是人们去寻找一种算法来证明某个非常困难的问题，可能很久很久都没有答案。也正是因为这个算法找不到，所以很多重大问题一直都被搁置，没办法得到满意的解答。一旦某天，某个神人找到了这个算法，并且行之有效，一个直接的后果就是之前许许多多百思不得其解的难题都被迎刃而解，不费吹灰之力！

NP问题以一个貌似不是数学专业的核心机密却占据了七大难题的榜首位置，不仅仅是因为这个问题空前的难度，更重要的原因是这个问题的真或者假，又或者是不可证明都会给人类带来巨大的改变，现在有更多具体的问题都已经证实了NP问题。遗憾的是，我们现在处在的阶段是，仅仅是知道如何区分P，NP，NPC问题，对于NP问题和P问题的边界判断成为这里最困难的部分。

也许我们未来的世界不存在蝴蝶效应

我们设想一下，以后的几百年里找到了那个绝世算法。那么我们的计算机就不会去走那么固定死板的道路，它就会选择性地去做一些有目的性的计算。它们能够在有限的时间里给出我们之前根本没法准确计算的结果，比如股票市场的预测，长期天气预报，开赛之前精准预言球赛比分，甚至我们会消灭“蝴蝶效应”，让这个世界上不存在混沌的状态。。。

这个梦想实在太过科幻，换个角度来思考，假如那天真的到来了，也许，我们的科技也走到了尽头了吧。