3.8　P和NP

让我们看看哪些问题让敌友国的研究者们头疼不已：团、哈密顿回路（“递棍儿2”）、地图填色，以及最大割。这些问题有一个共性，都可以用很简单的方法检查方案的有效性。一旦敌友国的科学家找到了阿尔法会的成员，就很容易验证是不是所有成员之间都互为朋友，即阿尔法会成员组成的是一个团。孩子们如果听说了一个能完成“递棍儿”游戏的方法，只要顺着方法玩一遍就知道对不对。随便给出一个涂色方案，政府很容易检查它是否符合相邻的房子颜色不同。在最后一个例子里，对于任意一个分组方式，校长只要数数有几对敌人被分开就能判断方案的好坏。

这一类能够很快验证一个解的有效性的问题，计算机科学家给它们起了一个名字：NP。如果你非想知道的话，这两个字母代表nondeterministic polynomial time（不确定性多项式时间）。团、哈密顿回路、地图填色和最大割都是NP中的典型例子。

与之形成对比的是P类问题，即我们能很快找到最优解的这些问题：最短路径、配对、欧拉回路（“递棍儿1”），以及最小割。

也许存在能快速找到团的高明算法。可能将来某个聪明的研究生能想出如何轻松找出哈密顿回路，或是一个最大化分割敌人到两个小组的快速步骤。也许团、哈密顿回路、地图填色和最大割也是在P类问题中的，就像最短路径、配对、欧拉回路和最小割一样。也许NP中的每个问题都有一个快速的解法，我们只是不知道而已。

这就是P/NP问题。P=NP意味着美好世界的到来，每个NP中的问题都对应一个有效的解法，也就是说每个有解的问题都能很快地验证给定解，并且快速地找到其中最优的解。与此相反，如果哪怕有一个NP中的问题我们找不到能给出快速解法的算法，那么P还是不等于NP。

判断P是否等于NP是计算机科学乃至整个数学领域最关键的问题。许多人呕心沥血，试图找到解决团、哈密顿回路或其他问题的好算法，可惜都失败了。与此相反，要证明P≠NP，必须证明无论现在还是将来，都不可能存在能够快速找到团或解决其他NP问题的算法。如何证明一件事不可能做成？目前这两个研究方向都没有什么实质性进展。

正是认识到了P/NP问题的重要性，克雷数学研究所才决定为解决它的人提供一百万美元的奖金。也正因为它无比关键，才促使我写出了这本书。