4.2　21个问题

库克的论文刚刚发表时，尽管结果的重要性得到了肯定，但也没有立即改变学术研究的方向。毕竟对可满足性问题感兴趣的人不多，并且大家对NP问题还不熟悉。斯蒂芬·库克甚至没有在论文中提到NP这个缩写，而用了它的全名“不确定性多项式时间”（nondeterministic polynomial time）。但不久以后，情况随着伯克利教授理查德·卡普的一篇承上启下的论文而改变了。

看过库克的论文以后，卡普意识到有一种方法可以把可满足性归约到团问题。卡普建立了一个简单的计算过程，它能把给定逻辑表达式转换成相应的好友关系图，并有当且仅当关系图上存在等于某个数的团时，表达式为真。任何能解决团问题的算法都可以用来解决满足性问题。库克表明了可满足性是NP问题中最难的。而卡普表明，团问题至少和可满足性问题一样难。这样一来，团问题就成为NP最难的问题之一。和可满足性问题一样，如果我们找到了团问题的快速解法，那么所有NP类问题就迎刃而解，从而证明P=NP。

库克表明了如何把类似团这样的问题归约到可满足性问题。卡普则表明可满足性可归约为团问题。这两个表面看上去非常不同的问题，在计算角度上竟然是相同的。可满足性容易计算的充分必要条件是团问题容易计算，而后者的充分必要条件是P=NP。

卡普不仅证明了团问题是NP中最难的问题之一，而且找出了其他19个同样难度的重要问题，包括分割难题、旅行推销员、哈密顿回路、地图填色以及最大割。只要有效解决了这些问题中的任意一个，你就能解决所有问题并证明P=NP。如果说P≠NP，那么这21个问题（包括可满足性问题）没有一个能被快速地解决。

卡普并不是凭空创造了这21个问题，对解决这些问题感兴趣的也不仅是数学家和计算机科学家。其中的许多问题来自现实世界。

比如可口可乐公司，它旗下的饮料品牌超过3000个，行销世界各地。一个可口可乐的灌装工厂可能会生产几百种不同的饮料产品。每个工厂都有数台机器需要进行一系列的作业，混合每种饮料所需的部分原料。这些机器可以生产各种产品，而灌装工厂需要合理调度机器的作业，以达到其吞吐量的最大值，从而在最短时间内生产出最多的饮料产品。这是一个作业调度问题，它也在卡普列出的21个问题之中，其求解难度不亚于任何其他的NP问题。

从电子计算机诞生之日起，科学家和程序员就在尽最大努力，研发解决作业调度问题的最佳算法，因为一个很小的调度改进就可能为某个企业节省数百万美元。还没有人写出对所有调度问题都能给出最好方案的算法。卡普证明，甚至连调度的简单改进也是一个难度不亚于任意NP问题的难题，这也立即揭示了为什么人们找不到那些调度改进算法。

不仅是大公司会关心这些问题。假设你带家人去迪士尼乐园春游，因为放假所以要排长队。你想尽可能多玩些好的娱乐景点，减少排队浪费的时间。《迪士尼乐园非官方指南》的作者想出了一整套如何减少等待时间的游玩攻略，但同时他们也承认自己在做一件很困难的事。

魔法王国景区21个景点一日游，针对成人的可能游览方案总数是让人震惊的51 090 942 171 709 440 000种。那可是超过5100亿亿种的组合，大概是地球上沙粒总数的6倍。要是再考虑上快速排号系统（FASTPASS）、游行、吃饭和休息等，就更复杂了，组合的数量还得增加好多。

类似的问题也困扰了科学家们很多年。 比如，快递公司会关心如何安排每个送货员的路线，让行驶距离最短，从而节省时间和燃料。 事实上，这类“如何以最小的代价访问多个地点”的问题十分普遍，人们给它们起了一个外号：旅行推销员问题。

许多科学家尝试过找出旅行推销员问题的最佳解法。还有人试过为作业调度问题找到一个高明的算法。另外人们还尝试过求解团、最大割以及其他卡普所列出的算法。卡普的论文意味着所有这些研究者研究的其实是一个问题，因为如果某人为其中某一个算法找出了有效的解法，那么所有其余的算法就迎刃而解了。

同理，所有这些独立工作的研究者之中没有一个人能对他们所研究的特定问题找到有效的解法，这很可能暗示了P≠NP，或者至少可以说，很难为这些问题中的任意一个找到好的算法。所以作业调度的技术员们可以理直气壮地告诉老板，我们是找不到机器上最好的作业调度方法，但不只是我们不行，连奥兰多的那帮机灵鬼都搞不定迪士尼乐园的游览线路规划呢。

而卡普的工作，一下子就把所有这些出了名的难以解决的计算问题联系到了一起。从此，P/NP问题成为众人瞩目的焦点。

每年计算机协会都会颁发ACM图灵奖，其地位相当于计算机科学界的诺贝尔奖。该奖得名于数学家阿兰·图灵，他在20世纪30年代为计算机科学奠定了基础。ACM将1982年的图灵奖授予斯蒂芬·库克，以表彰他为P/NP问题的建立所做出的杰出贡献。但一个图灵奖还不够，理查德·卡普于1985年也获得了图灵奖，奖励他在算法理论方面的杰出工作，特别是列出了21个NP完全问题。