计算机是理性的典范，它可以轻松完成人类无法完成的计算。但是对于一些形式非常简单的问题，计算机却无法让人满意--它们需要我们无法接受的时间和资源。
被一个傻瓜扔进海里的石头，派十个聪明人也捡不回来。
——意第绪（Yiddish）谚语
每一位自然哲学家用来指引人生的座右铭都应该是，追求简洁，然后不信任它。
——阿尔弗雷德·诺思·怀特黑德（Alfred North Whitehead，1861—1947）
我不喜欢悖论，而且我认为那些喜欢悖论的人既没有文化，也缺乏智慧。
——拉希德·埃尔戴夫（Rashid al-Daif）
计算机是理性的典范。它们是毫无心肝的机器，一丝不苟地严格遵守逻辑的法则。计算机没有任何感情用事或者优柔寡断的可能：它们只会在逻辑的规定下完全按照命令行事。计算机是逻辑的引擎，我们正是从这个角度来看待这些机器的，并由此判断它们能够和不能够完成什么样的任务。我们都对计算机能轻松做到和不能轻松做到的事情有直观的感受。它们可以轻易地求出一长串数字的和，也可以对海量记录进行排序整理，对于其他简单任务的处理更不在话下。然而令人惊讶的是，对于一些形式非常简单的问题，计算机却无法令人满意地将其解决。在这一章，我将介绍若干问题，计算机在理论上可以解决这些问题，但在实践中则需要极为庞大的时间和资源。我还会解释为什么这些问题看上去如此困难，以及为什么研究者相信它们永远都无法被轻易地解决。
在本章第1节中，我将陈述几个相对简单的问题。在探讨这些简单问题的过程中，你将逐渐熟悉下面两章使用的语言和符号。第2节包括5个困难问题的例子。我将证明虽然这些问题的形式很简单，但它们并不容易解决。第3节指出，这些问题都是彼此相关的。你还会看到为什么它们没有简单的解决方案。在第4节中，我将揭示如何应对这些困难的问题。它们总是无法被解决的，但有时候我们可以近似估计它们的解决方案。我以第5节作为结尾，并在这一节中讨论了甚至更难的问题。在下一章中，我的焦点会放在某些形式非常简单的计算机问题上，无论花多少时间或者动用多少资源，这些问题都无法解决。
摘自Al-Daif（2000，4）。
简单，但算不出答案
任何曾在过去的10年里使用过计算机的人都知道它们正在变得越来越快。曾经需要几个小时完成的事情现在只需要几秒。曾经需要几秒完成的事情现在几乎只需要一瞬间。我们对个人计算机的处理速度已经失去感觉了。有些人懒得打理电子邮件收件箱，尽管里面有10000条信息等待删除。只需要轻轻点击一个按钮，一个现代收集癖就能在几秒钟之内完成这10000条信息的排序。一切发生得如此之快，我们甚至不会意识到计算机在工作。在这一章，我们将看一看计算机完成排序和其他简单任务需要多大的工作量。我们还将审视一些需要极大工作量的问题，由于工作量巨大，这些问题无法在可行的时间内完成。首先让我们细心观察某些容易的问题。
加法和乘法运算
上小学四年级的时候，孩子们会学习好几位数的加法和乘法运算。学生们必须遵守他们学到的标准程序，这样才能得到正确答案。用来称呼某种标准程序或指令序列的术语是算法（algorithm）。这个词来自穆罕默德·伊本·穆萨·花剌子模（Muhammad ibn Mūsā al-Khwārizmī，780—850），他撰写了第一本教导西方世界进行代数运算的书。我们将在下文描述和分析解决不同问题的各种算法。
让我们先从简单的开始。要将两个7位数相加，必须将每一位的数字两两相加（并且记得进位），一共是7对，见图5.1。
图5.1 两个7位数相加
无论在任何情况下遇到某种算法，我们都必须搞清楚这种算法需要多少基本操作。所需操作的数量取决于问题的大小。对于两个7位数，需要7步操作。对于两个42位数，需要42步操作。一般而言，要让两个n位数相加，必须逐步将n对每位数字相加。
乘法与加法又有不同。将两个7位数相乘，必须用第一个数字每一位上的数乘以第二个数字每一位上的数。完成这个步骤并将所有结果都排列在恰当的位置后，还要将这些数字再加起来，如图5.2所示。
图5.2 两个7位数相乘
与加法相比，乘法运算需要更多操作。对于第二个数字的7位数字中的每一个，我们都必须进行7次乘法运算，所以一共需要7×7=72=49次相乘（忽略最后的加法运算）。一般而言，对于两个n位数字，我们需要用第一个n位数字每一位上的数乘以第二个n位数字每一位上的数字。因此我们总共需要进行n2次乘法运算。n2通常比n大——正如我们将会看到的那样，但是它仍然不是很大。
完成这些任务需要多少时间呢？答案取决于计算机的速度。计算机越快，需要的时间就越少。然而，我们将在下面看到，计算机的速度其实并不那么重要。让我们来做一些计算吧。比如我们想将两个100位数字相乘。这就需要1002=10000次操作。无论我们的计算机每秒能进行10万次还是100万次操作，我们的任务都将在不到0.5秒内完成。很显然，最重要的与其说是计算机的速度，不如说是需要多少基本操作。我们将在下文中看到，虽然乘法运算相对简单，但两个数相乘的反面——也就是将一个数拆分成两个因数——就难多了。
搜索
想象一下你有一个装满了文件夹的文件柜，每个文件夹里都是关于一支乐队的信息。假设这些文件夹的排列没有任何顺序。现在，让我们假设你想找到与某支乐队相关的那个文件夹。这无异于在干草垛里找一根针。找到目标文件夹的唯一方法是将所有文件夹逐个检查一遍。这种搜索方法称为穷举搜索算法（brute-force search algorithm）。如果文件柜里有n个文件夹，你必须搜索多少文件夹呢？运气好的话，也许你尝试几次就能找到想要的文件夹。然而在最坏的情况下，你必须搜索全部n个文件夹才能找到自己想要的那个，或者发现目标文件夹根本不在文件柜里。所以对n个无序元素进行穷举搜索可能需要n次操作。
假设文件柜中关于各乐队的文件夹是严格按照字母顺序排列的。对于这个有序文件柜，你仍然可以像对待无序文件柜那样执行同样的穷举搜索。如果你寻找的是关于ABBA乐队的文件夹，那么穷举搜索就会让任务完成得很顺利。然而，如果你要找的是ZZTop乐队的文件夹，你就会浪费很多时间。我们感兴趣的是在所有情况下工作量最少的算法。让我们尝试另一种算法，它名为二分搜索算法（binary search algorithm），它需要将一堆文件夹分成两堆。在搜索某个文件夹时，不是从第一个文件夹开始向后逐个搜索，而是从中间的文件夹开始，看看目标文件夹位于它的前面还是后面。假设我们要找的是Pink Floyd。我们会先看中间的文件夹，比如说Madonna，既然Pink Floyd在字母表上的顺序位于Madonna之后，我们会忽略从开头到中间的所有文件夹，然后只关注从Mariah Carey开始到ZZTop结束这部分的文件柜。我们可以用表5.1的第一列描述这次搜索。我们在分割文件夹——用来比较的文件夹——旁用*标注。
表5.1 对有序清单的二分搜索
（续表）
我们的下一个猜测项位于文件柜中这一部分的中央：这一次是Prince。由于Pink Floyd在Prince前面，所以我们将忽略从Rod Stewart到ZZtop的所有文件夹，只关心从Mariah Carey到Prince的文件夹。我们继续使用这种二分法，直到我们在第四次猜测中找到了我们喜欢的Pink Floyd乐队的文件夹。
我们必须要进行多少次比较呢？如果我们开始的时候有n个文件夹，经过一次检查，我们会丢弃大约n/2个文件夹，关注剩下的n/2个文件夹。又一次检查之后，我们只剩下n/4个文件夹需要考虑。我们按照这种方式继续下去，直到只剩下一个文件夹，然后我们看它是否是目标文件夹，也就是说我们看看我们想要的文件夹是否在文件柜里。对于某个数值n，n可以被不断均分的次数用对数函数表示，写成log2n。所以二分搜索算法只用检查log2n次。
让我们看看使用这种算法的一些案例吧。对于n=256，我们可以进行下列二分：
128，64，32，16，8，4，2，1。
既然有8次分割，所以我们说log2256=8。对于n=1024，我们有
512，256，128，64，32，16，8，4，2，1。
所以log21024=10。最后，对于n=65536，我们有
32768，16384，8192，4096，2048，1024，512，256，128，64，32，16，8，4，2，1。
既然有16次分割，所以我们说log265536=16。
对于n=1000，穷举搜索算法在最糟糕的情况下需要进行1000次检查，而二分搜索算法需要进行log21000次检查，也就是大约10次检查。这是巨大的进步。
对于某个特定的问题，可能存在几种不同的算法可以用于提供解决方案。有时候某些算法应该用于某些特定类型的输入，而另外一些算法应该用于其他类型的输入。我们已经见到，文件柜有序或无序的情况是存在差别的。穷举搜索算法应该用于无序文件柜，而二分搜索算法应该用于有序文件柜。对于每个问题，我们都将分析不同的算法，并试图找到最有效的算法。对于一个问题而言，在最糟糕的情况下能够解决它的最有效的算法才是最根本性的。所以我们说，搜索无序清单需要n次操作，而搜索有序清单需要log2n次操作。
排序
我们在上一个例子中看到，保持事物整洁有序是有回报的。对于一连串的n个元素，应该如何对它们排序呢？有很多不同的算法可以执行这个任务，但我要在这里陈述最简单的一种。选择排序算法（selection-sort algorithm）的操作步骤如下：
1.搜索全部元素，找到最小的元素。
2.将这个最小的元素与清单中第一个元素调换位置。
3.搜索清单的剩余部分，找到其中最小的元素。
4.将该元素与清单的第二个元素调换位置。
5.以这种方式继续，直到所有元素都位于各自正确的位置上。
我们以3个字母构成的单词为例，按照字母表顺序排列它们，以便将这种算法形象地表示出来，如图5.3所示。
这种算法的工作量是多少呢？为了得到所有元素中最小的，我们需要查看所有n个元素。为了找到除了第一个元素之外所有元素中最小的，我们需要查看n–1个元素。我们能够看出，按照这种方式继续下去，要将选择排序算法全部执行完毕的话，一共必须查看
图5.3 选择排序算法的步骤
n+（n–1）+（n–2）+…+2
个元素。它们的和大约为n2的一半，于是我们说选择排序算法最多需要n2次操作。
其他更加精密的排序算法需要的操作次数较少，其中之一称为合并排序算法（merge-sort algorithm）。我们不需要了解合并排序算法的原理。只需要知道对于大小为n的输入，这种排序算法需要
n×log2n次操作。例如，对于大小为1000的无序清单，合并排序算法能够在
1000×（log21000）=1000×10=10000次
操作后完成对清单的排序。
你也许会认为n2和n×log2n没有多大差别。或许并不值得费力气使用这种高级算法。然而绝对值得！思考一下布鲁克林区400万个电话号码的排序任务。对于400万个条目的排序，n2算法必须执行16万亿次操作。相比之下，如果使用更高效的n×log2n算法来对这400万个条目排序，大约需要8800万次操作。这是巨大的进步。
欧拉回路
柯尼斯堡（Königsberg）是曾经属于普鲁士的一座俄罗斯城市。这座城市横跨普里高里河（Pregel River）两岸，河中央坐落着奈佛夫岛（Kneiphof Island）。这座城市的主要城区和这座岛由七座桥彼此相连，如图5.4所示。
图5.4 柯尼斯堡的七座桥
城市里的居民一度想要知道，他们是否有可能从城市中的某一点开始漫游，走过七座桥梁中的每一座且只走过一次，最后回到最初的起点。试试寻找一条这样的路径吧。
1736年，所有时代最伟大的数学家之一莱昂哈德·欧拉（Leonhard Euler，1707—1783）面临着这个问题。他意识到要找到这样一条穿过七座桥的路径，我们并不关心行人会不会停下来买冰激凌，慢悠悠地闲逛，去烤肉野餐，还是花三天时间完成旅程。要紧的是每块土地和桥梁之间的连接方式。他注意到可以将每块陆地想象成一个点。同样无关紧要的是这些桥梁有多宽，或者它们的年代有多久远，或者它们彼此之间距离有多远。唯一有意义的信息是这些桥梁连接的是哪块土地。可以将每座桥梁想象成连接两点的一条线。我们可以在柯尼斯堡的地图上画出这些点和线，如图5.5所示。
图5.5 柯尼斯堡和代表其桥梁的草图
在这种洞察力之下，欧拉开创了被称为图论（graph theory）的数学领域。这里的图指的是若干给定的点之间的一系列点和边（线）构成的图形。
这种图形描述了事物之间的关系。由于“事物”是普遍的，图论的应用非常广泛，并且已经成为最重要的数学分支之一。例如，图论可以描述计算机网络：点对应的是计算机，两点之间的边对应的是计算机之间的连接。另一个例子是万维网（World Wide Web）：图形的点可以代表网页，边代表两个网页之间的连接。地铁示意图是这种图形的另一个常见例子。
下面是图论的一个有趣的应用。思考这样一个图形，它的点对应地球上的每一个人。在任意两个认识的人之间画一条线。研究者相信在这个图形中，连接任意两点最多只需要6条线。这意味着对于世界上的任意两个人，都存在某个链条，令第一个人认识某人，某人认识某人，某人……某人认识第二个人。这个链条一般来说不需要超过6个人。这个法则被称为“六度分隔理论”（six degrees of separation）。
让我们回到柯尼斯堡七桥问题上来。一旦欧拉忽略了这个问题中不重要的部分，他就能很容易地看出这样的路径不可能存在。欧拉的推理是，每次有人进入一块陆地或一个点，他们必须能够离开这个点。当然，他们还可以再次来到这个点，但之后必须再次离开。欧拉意识到，这条路径的存在需要每个点必须有偶数条边与其相连。如果满足了这个要求，就会存在一条路径从某一点出发，经过每条边且只经过一次之后重新回到起点。如果不满足这个要求，那就不存在这样的路径。既然图5.5中的每个点都有奇数个边/桥与其相连，那就不可能存在这样的回路。
关心这个问题并不一定非得考虑普鲁士古城里的漫游者。对于任何图形，我们都可以将开始和结束于同一点的路径称为一个回路。通过每一条边且只通过一次的回路称为欧拉回路。所以对于任何图形，我们都可以问问是否存在欧拉回路。这就是欧拉回路问题（Euler cycle problem）。我们可以看出，图5.6中的图形不包含这样的回路。
图5.6 柯尼斯堡七桥问题的图形
注意每个点都有奇数条边与其相连。相比之下，思考图5.7中的图形。每个点都有偶数条边与其相连，因此存在欧拉回路。（试着找一找！）
图5.7 经过修正的柯尼斯堡七桥问题
我们可以放弃开始和结束于同一点的要求，从而提出欧拉路径问题：对于一个图形，是否存在一条路径穿过每一条边且只穿过一次，但不需要开始和结束于同一点？理解了欧拉对欧拉回路的要求之后，欧拉路径问题的答案显而易见：如果某个图形中至多两个点有奇数条边与其相连，而其余的点有偶数条边与它们相连的话，就存在这样的欧拉路径。这两个点将会是目标路径的起点和终点。思考图5.8中的图形。它存在从顶部点到底部点（反之亦然）的欧拉路径，但是不存在欧拉回路。
图5.8 有欧拉路径但没有欧拉回路的图形
这与计算机和算法有什么关系呢？如果没有前面几个段落提供的信息，我们可能会认为要想判断某个图形是否存在欧拉回路，我们必须尝试所有可能的回路，并查看是否有任何回路能够经过每一条边且只经过一次。对于比较大的图形，会有数量极多的回路需要查看。现在有了欧拉的技巧，我们就有了判断是否存在欧拉回路的新方法。这种技巧只需要让我们核查每个点是否有n条边与其相连，这只要相对较少的操作次数就能完成。欧拉的方法给我们节省了许多工作量。我们将一直寻找这样的技巧。
本节陈述的所有问题都可以用某种算法解决，这些算法的操作步骤的次数可以用多项式表示，如n,n2，或者n×log2n。这些问题称为多项式问题（polynomial problems）。所有多项式问题的合集用P表示。现代计算机可以在可行的或易掌控的操作次数内解决大部分多项式问题。这些问题可以在一段可行的时间内解决。
和这里讨论的具有可行性的问题不同，我们将在下一节审视不可行或难以驾驭的问题，即在一段合理的时间内无法解决的问题。
布鲁克林目前有250万人。由于网络的快捷高效，现在真的没什么人用电话号码簿了。
岛上有柯尼斯堡最著名的居民伊曼努尔·康德的坟墓。
等不到的解答
要想感觉某些问题有多难，让我们先介绍下面5个问题，它们都很容易被描述。
旅行推销员问题
假设有一名推销员想开车去美国的6座特定城市。他想每个城市都只去一次，而且在结束旅行的时候回到出发的那座城市。有很多不同的路线可供选择。我们的这位旅者很节俭，为了节省时间和金钱，他想找到路程最短的路线。他查找这些城市之间的距离，并在表5.2中发现了这些信息。
表5.2 美国部分大城市之间的距离
既然我们已经知道了关于图形的知识，我们可以在图5.9中用图形将同样的信息表示出来。
图5.9 各城市之间距离的完整加权图
每条边上的数字代表城市之间的距离。这样的图形称为加权图（weighted graph），因为各条边的长度都进行了加权。因为每两点之间都有一条边，所以我们说这张图是完整的。
问题是哪条穿过所有城市的路线是最短的？处理这个问题的一种方法是选择任意一条穿过所有6座城市的路线，将相邻城市之间的距离加起来（别忘了回到最初的起点），然后看总距离是多少。计算完成之后，尝试另一条可能的路线，将所有距离相加，看看这次是不是更短。为了确保得到最短的路线，你必须对所有可能的路线进行穷举搜索。
一共存在多少可能的路线需要查看呢？我们必须搜索这6座城市所有可能的顺序或排列。让我们数一数有多少种排列方式吧。作为起点的城市存在6种可能。当你来到第一座城市之后，由于你不想返回同一座城市，所以第二座城市就剩下了5种可能。而下一个目的地你就只有4座城市可以选择。按照这种方式继续，我们发现你必须全部搜索的可能路线的数量是6×5×4×3×2×1=720。
这是很大的工作量，但是在现代计算机的运算下，检查所有720种可能的路线可以在数微秒之内完成。
让我们从更具普遍意义的视角看待这个问题。假设我们的旅行者想造访n座城市。我们可以将这个问题表示为拥有n个点的图形。在任意两个点之间，都有长度经过加权的边代表两座城市之间的距离。于是我们得到了拥有n个点的完整加权图，我们想找到经过每座城市（点）且只经过一次，最后回到起点城市的最短路径。使用和上面同样的推理过程：第一座城市有n种可能，第二座城市有n–1种可能，……总之，必须查看的可能路线的数量是
n×（n–1）×（n–2）×…×2×1。
我们将这个数字写成n!，并将该函数读作“n阶乘”。关于这个函数有一个令人惊叹的事实，随着n的变大，n!会大得令人难以置信。
让我们撸起袖子做一点计算吧。对于n=100，存在多少路线呢，一台性能合理的计算机搜索所有这些可能的路线需要多久呢？我们需要计算100！。我们可以坐下来，用100乘以99乘以98乘以……乘以3乘以2乘以1。我们也可以偷懒，在每台计算机里都带有的科学计算器里输入这个阶乘。我们会得到下面的结果：
100!= 93 326 215 443 944 152 681 699 238 856 266 700 490 715 968 264381 621 468 592 963 895 217 599 993 229 915 608 941 463 976 156 518 286253 697 920 827 223 758 251 185 210 916 864 000 000 000 000 000 000 000000。
在你开始晕头转向之前，让我们花一分钟时间看看这个数字。它以9开头，后面跟着157位数字。有一个非常大的数字叫作古戈尔（googol），是1后面跟着100个零。我们的这个数字比古戈尔大得多。它是一个难以想象的大数。
对于这些潜在路线中的每一条，我们都必须将这100个城市之间的距离加起来，将总和与已经得出的最短距离比较。假设我们拥有一台每秒钟能检查100万条路线的计算机。那么用100！除以100万，我们会得到
93 326 215 443 944 152 681 699 238 856 266 700 490 715 968 264 381 621 468 592 963 895 217 599 993 229 915 608 941 463 976 156 518 286 253 697 920 827 223 758 251 185 210 916 864 000 000 000 000 000 000秒。
要想知道这是多少分钟，我们必须再除以60，得到
1 555 436 924 065 735 878 028 320 647 604 445 008 178 599 471 073 027 024 476 549 398 253 626 666 553 831 926 815 691 066 269 275 304 770 894 965 347 120 395 970 853 086 848 614 400 000 000 000 000 000分钟。
再次除以60，我们会得到
25 923 948 734 428 931 300 472 010 793 407 416 802 976 657 851 217 117 074 609 156 637 560 444 442 563 865 446 928 184 437 821 255 079 514 916 089 118 673 266 180 884 780 810 240 000 000 000 000 000小时。
再除以24，我们得到
1 080 164 530 601 205 470 853 000 449 725 309 033 457 360 743 800 713 211 442 048 193 231 685 185 106 827 726 955 341 018 242 552 294 979 788 170 379 944 719 424 203 532 533 760 000 000 000 000 000天。
我们还要继续吗？再除以365就是
2 959 354 878 359 467 043 432 877 944 452 901 461 527 015 736 440 310 168 334 378 611 593 658 041 388 569 114 946 139 776 006 992 588 985 721 014 739 574 573 764 941 185 024 000 000 000 000 000年。
除以100，我们得到
29 593 548 783 594 670 434 328 779 444 529 014 615 270 157 364 403 101 683 343 786 115 936 580 413 885 691 149 461 397 760 069 925 889 857 210 147 395 745 737 649 411 850 240 000 000 000 000世纪。
这是2.9×10142个世纪。这是很长的一段时间，长得令人震惊！
我们需要沉思片刻。旅行推销员问题是一个看上去非常简单的问题，可以向任何一个小学生解释清楚，而且对于数值较小的输入，任何人都可以在几秒之内解决问题。但是当输入数值更大时，所需操作次数会变得极为庞大。没错，这个问题能够解决，但我们无法说一台计算机可以在一段合理的时间内“解决”这个问题。
我们得到一个输入并需要找到最短或最长或最佳解决方案，这样的问题称为最优化问题（optimization problem）。计算机解决的很多问题都是最优化问题。和我将在本章剩余部分提到的所有其他问题一样，旅行推销员问题还存在另一种形式，名为判定问题（decision problem）。判定问题只需要计算机给出是或否的答案。这些问题不关心最短、最长或最佳的解决方案。相反，它们只关心某种类型的解决方案是否存在。例如，找到美国速度最快的跑步运动员就是一个最优化问题。与之相关的判定问题可能是，“美国是否有任何跑步运动员可以在3.5分钟内跑完一英里？”这样的问题需要“是”或“否”的答案。
旅行推销员问题的判定问题形式如下：对于某个完整的加权图形和某个整数K，是否存在一条路径穿过该图形的每个点，令路径的总长度小于或等于K。如果存在一条路径小于或等于K，回答“是”。如果不存在，回答“否”。注意我们不需要找到这条路线。值得一提的是，判定问题有比最优化问题更迅速地得到解决的潜力。在判定问题中，如果我们发现了我们正在寻找的方案，我们就可以停下来，给出肯定的回答。相比之下，为了寻找最优方案，最优化问题必须检查所有可能的路线。不过我们在本节和下一节将主要关注判定问题。
旅行推销员问题一定说明了人类认知能力的某种局限。即使是体量相对合理的问题，人也不可能知道最短的路径是什么。
哈密顿回路问题
这个问题也和贯穿既定图形的路线有关。对于某个图形（我们不需要它是加权的或完整的），我们要在其中寻找一条穿过每个顶点且只穿过一次，最后回到起点的连续路线。这样的回路称为哈密顿回路（Hamiltonian cycle）。哈密顿回路问题的判定版本是，判定某给定图形是否存在哈密顿回路。该问题在真实世界中存在许多应用场景。例如，一位公共汽车司机会拿到一张城市地图，被告知去若干既定地点接学生上车。司机能够在不重复经过任何一点的情况下完成这个任务吗？思考图5.10中的两个图形。
图5.10 哈密顿回路问题的例子
在左边的图形中，可以从任意一点开始，顺时针或逆时针画线，就能得到一个哈密顿回路。作为对比，尝试在右边的图形中找到一条这样的回路。（不存在。）
解决这个判定问题的一种方法是在既定图形中尝试穷举搜索所有可能的排列。对于每一种排列，查看它是否在图形中满足哈密顿回路的要求。对于大小为n的图形，一共有n!种可能的排列。正如我们在旅行推销员问题中见到的那样，这远远不能令人满意。对于任何稍大的输入而言，都没有足够的时间来解决这个问题。我们能比n!算法做得更好一些吗？
哈密顿回路问题和欧拉回路问题之间有某种相似性。我们都会得到一个图形，尝试在其中寻找一条回路。在哈密顿回路问题中，我们找的是经过每个点且只经过一次的回路，而在欧拉回路问题中，我们找的是经过每条边且只经过一次的回路。在上一节中，我们看到欧拉教给我们一个很酷的技巧来判断某既定图形中是否存在欧拉回路：只需确保与每个点相连的边是偶数条即可。有没有类似的技巧告诉我们某既定图形中是否存在哈密顿回路呢？遗憾的是，以作者的愚见，并不知道存在这样的技巧，其他任何人也应该不会知道。这一次，对于拥有n个点的既定图形，判断其中是否存在哈密顿回路的唯一方式是对所有n!条可能的回路进行穷举搜索。所以虽然这两个问题是相似的，但其中一个很容易解决，另一个则看起来很有难度。每个呈现在我们面前的问题都必须小心检查。
只是因为我们不知道比穷举搜索更好的算法，并不意味着不存在这样的算法。某一天也许有人会发现这样的算法。然而我将在下一节中解释，为什么大部分研究者都相信这样的算法不存在。
集合划分问题
假如我们有一个班级，班上学生的年龄分别是{18,23,27,65,22,25,19,21}。我们想把他们分成拥有同样多“生命体验”的两群。稍微思考一下，就会发现{18,27,65}和{23,22,25,19,21}这样的划分方式能够满足要求；两边的年龄加起来都是110岁。这就是集合划分问题的例子。对于一系列正整数构成的集合，判断这些数字是否能划分到两个集合中，令两个集合中所有数字之和相等。
让我们看看这个问题的其他一些例子。集合{18,23,28,65,22,25,19,21}的情况如何呢？这些数字和上面几乎一样，只不过我们用一个28岁的学生代替了一个27岁的学生。这个集合不可能划分成相等的两部分。在上一个例子中，所有数字之和是220，我们能将它们分成两个集合，每个集合包含110。在这个例子中，所有数字之和是221。不可能把奇数221分成两个相等的整数。所以判断不存在解决方案的一种方法是将所有数字加起来，看结果是不是奇数。如果是奇数，我们就能断定不会存在解决方案。但如果这个总和是偶数呢？
思考集合{30,4,32}。这三个数字的总和是66，这是一个偶数。然而，很显然没有办法将这个集合分成两个相等的部分。所以我们查看所有数字之和是奇数还是偶数的方法并不总是有效。它们的和可以是偶数，但这些数字仍然无法划分成相等的两部分。
应该如何着手解决此类问题呢？我们必须检查该集合所有可能的划分方式。对于每种划分方式，我们需要将其中一部分相加求和，看看结果是否等于所有元素之和的一半。一共存在多少种划分方式呢？对于某既定集合的每个元素，我们可以将该元素放进一个集合或另一个集合中。所以第一个集合有2种可能，第二个集合有2种可能……第n个集合有2种可能。总共是
种可能。我们可以说这个问题的工作量是呈指数级增长的。
假设我们想将100个数字分成相等的两堆。我们必须检查多少种可能的划分方式呢？计算一下就知道一共有
2100=1267650600228229401496703205376
种划分方式。如果我们有一台每秒钟能够检查100万种划分方式的计算机，我们仍然需要
1267650600228229401496703205376/1000000=1267650600228229401496703秒。
除以60，得到21127510003803823358278分钟。再次除以60，得到352125166730063722637小时。这相当于14671881947085988443天或40196936841331475年或401969368413314个世纪。这可不是我们等得起的时间啊！
你也许会思考，这个问题是否存在不一样的、更快的解决方法。然而，没有任何已知方法能够在所有情况下以更短的时间解决这个问题。一定能够找到解决方案的唯一已知的方法就是查看所有2n个子集的穷举搜索法。
子集和问题
与集合划分问题类似的是子集和问题。假设你准备去乡下度几天假，正在把行李打包装上车。很多东西你都想带，但你的车容量有限。你想带上足够多的行李，刚好把你的车塞满。这个常见的场景就是子集和问题的非正式版本：对于某个由若干整数构成的集合和某个整数C（容量），判断该集合是否存在某个子集，令其元素之和正好等于C。例如，思考集合{34,62,85,35,18,17,52}和容量C=115。如果你对这个集合付出足够长的时间，你会意识到它的子集{62,35,18}的各元素之和等于115。如果我们将C改成114或者改动集合里的这些整数的话，会发生什么呢？
一般而言，面对一个整数集合和一个整数C，计算机该如何着手解决这个判定问题呢？正如在集合划分问题中一样，我们可以筛选该集合的所有子集，而且对于每个子集，求各元素之和看是否等于C。我们已经知道，对于含有n个元素的集合，其子集数量为2n个。因此如果输入的数字较大，解决该问题需要的操作数量和集合划分问题同样庞大，也同样需要不切实际的漫长时间。
可满足性问题
这个问题涉及简单的逻辑命题。我们要使用基础逻辑的一些基本知识和运算符∧（与），∨（或），~（否），以及→（蕴涵）。思考下列逻辑命题（p∨~q）→~（p∧q）。
这个陈述可能是真的，也可能是假的，这取决于变量p和q的赋值。例如，如果我们令p为真，q为假，那么整个命题就是真的。然而，如果我们令p为真，q为真，那么整个命题就是假的。如果一个逻辑命题可以通过变量赋值的方式为真，那么它就是可满足的（satisfiabl）。可满足性问题问的是，对于某个给定的逻辑命题，是否存在某种为变量赋值的方式，令整个命题为真（即可满足）。我们看到上述逻辑命题是可满足的。思考下列命题：
a∧（a→b）∧（b→c）∧（~c）。
要想让这个命题为真，我们必须令a为真且（a→b）为真。根据演绎推理，我们必须令b为真。继续看（b→c），c也需要为真。但c为假，因为~c必须为真。总之，没有办法令这个命题在符合逻辑的情况下为真。
可满足性问题该如何着手解决呢？大部分高中生都知道，要判断一个逻辑命题的值，需要先构建一张真值表。这个问题的决策版本是，某个逻辑命题的真值表是否存在其值为真的一行。
解决这个问题的一种算法是为既定命题构建一张真值表，并检查每一行的赋值情况，查看是否有任何一行其值为真，并根据结果反馈是或否的答案。然而构建这样的真值表需要大量工作。如果给定逻辑命题中有2个变量，那么它的真值表就有4行。如果有3个变量，那真值表就有8行。总的来说，对于拥有n个不同变量的命题，它的真值表会有2n行。工作量的指数级增长说明这个问题和本节讨论的其他四个问题一样难以解决。
既然我们已经见证了一些例子，现在让我们提出一个严格的定义吧。我们将所有需要2n、n!或更少操作次数才能解决的决策问题表示为NP。NP中的问题称为“NP问题”。既然P是多项式操作次数内可解决的问题，而多项式的增长速度远低于指数或阶乘函数，所以我们知道P是NP的子集。也就是说，每个“容易的”问题都是所有“难的和容易的”问题中的一个元素。
你可能会有所疑虑，多项式函数与指数或阶乘函数之间真的存在差别吗。表5.3应该能够打消任何疑虑。
表5.3 多项式函数和非多项式函数的若干值
前面几列显示了一些典型的多项式函数和n取不同数值时它们的值。最后两列显示了指数函数和阶乘函数的值。虽然当n的数值较小时，某些多项式函数大于最右边两列，但是当n=50的时候，多项式函数就再也赶不上其他函数了。似乎正是这种迅猛的增长在多项式函数和非多项式函数之间划出了一道清晰的界限。
自从NP问题在20世纪70年代初得到定义以来，研究者们已经发现了成千上万个这样的问题。NP问题出现在商业、工业、计算机科学、数学、物理学等领域的方方面面。它们和调度、路由选择、图论、组合数学以及其他许多主题有关。最近，和基因测序相关的许多生物学问题也被发现是NP问题。随着生物学家能够读取人的DNA（脱氧核糖核酸）并使用这些信息定制药物，他们意识到有些任务似乎需要更多的操作步骤和更多的时间。
并非所有局限都是不好的。我们在第1节中看到，将两个数相乘是多项式问题。相比之下，将一个数字分解成两个因数就相当困难了。思考4871乘以7237。任何一个聪明的四年级小学生都能很快得到35251427的答案。现在思考38187637这个数字。这个数字是两个质数（也就是不能被除了1和自身之外的数整除的数）相乘的结果。你能找出这两个质数吗？一个人或一台计算机需要很长时间才能意识到它的两个因数是7193和5309。原因在于虽然乘法是n2问题，但因子分解却是一个NP问题。这种不对称性被用来在网络中发送秘密信息。我们不会探讨与如何做到这一点相关的繁杂细节，但的确有一种算法使用大数字秘密传送信息。这种算法在1978年被罗恩·李维斯特（Ron Rivest）、阿迪·沙米尔（Adi Shamir）和伦纳德·艾德曼（Leonard Adleman）描述，名为RSA（一种非对称加密算法）。如果有窃听者在偷听一段对话，他们必须对一个非常大的数进行因子分解，否则无法理解对话中的信息（或者获得这段对话中包含的信用卡号码）。由于这是个非常难的问题，我们的安全系统才是牢固的。如果大反派莱克斯·卢瑟（Lex Luthor）某天发现了能够轻松分解因子的算法，RSA就会被破解，万维网的很大一部分安全措施就会毫无用处。
我们已经看到，对于本节描述的所有5个问题，任何数值较大的输入基本上都无法解决，也就是说，无法用我们今天的计算机在一段合理的时间内解决它们。你也许会试图忽略这些局限，指望着当计算机的速度变得越来越快，NP问题也会变得越来越容易解决。可惜，这样的希望注定要落空。正如我们在上文中看到的那样，旅行推销员问题在n=100这样相对较小的输入时，就需要2.9×10142个世纪才能解决。即使我们将来的计算机比现在快10000倍，我们的问题仍然需要2.9×10138个世纪。这仍然是无法接受的一段时间。结论：更快的计算机也无法帮助我们。
类似地，随着我们的多处理技术和能力的进步，也就是说，随着我们使用多个处理器并联工作的能力有了进步——我们也许会对NP问题的整个概念不屑一顾。你可能会认为这些问题对于每次只能执行一个步骤的单处理器而言是困难的，但是有了许多处理器一起工作，也许可以在合理的时间内完成任务。这种希望也是徒劳的。即使有10000个处理器同时工作，所需时间也不会少于2.9×10138个世纪，这样的时间需求仍然是不可接受的。让我们再激进一点儿。科学家估计宇宙中一共有1080个原子。假设宇宙中的每个原子都是一台计算机，它们共同解决这个问题的不同部分。用这种方法分割这个问题，所有这些计算机仍然需要工作1062个世纪才能全部解决这个问题。况且这还是输入数值为100时的情况，如果是更大的输入呢？结论是，使用任何机器也无法在任何合理的时间段内解决这样的问题。
你也许曾经注意到媒体对量子计算机的报道。目前它们是假想中的设备，致力于使用奇怪且违反直觉的量子力学增强我们的计算能力。量子力学最奇特的观念之一是亚原子物体可以同时出现在不止一个位置。虽然常规大小的物体要么在这里，要么在那里，但是亚原子物体有叠加态——它们可以同时位于多个位置。无论你对这种观念有多么怀疑，叠加态是在我们的宇宙中客观存在的事实。量子计算机科学家试图利用叠加态制造更好的计算机。对于大量可能的解决方案，常规计算机每次只能搜索其中的一个。相比之下，量子计算机可以将自身置于搜索状态的叠加态中，一次检查多个可能的解决方案。你可能会觉得量子计算机的方案会让NP问题更容易解决，但这样的希望又是泡影。人们发现当量子计算机在大小为n的清单中搜索某一特定元素时，它最少需要个步骤。所以在搜索NP问题的所有2n个可能的解决方案时，量子计算机可以在个步骤内完成任务。然而，
仍然是指数函数。所以量子计算机不是我们期盼中的NP问题的解决方案。
总而言之，在这些NP问题面前，所有可预见的计算机科学的未来进步都是无能为力的。轻松解决这些问题的唯一方式是为它们找到完善的多项式算法。我们将在下一节指出，为什么大多数研究者都相信这些问题没有更好的算法。似乎在将来的一段合理时间内，它们将继续成为无法解决的问题。这些问题之所以难，不是因为我们缺少解决它们的技术。它们之所以难，是因为它们本身的性质。这种困难是它们固有的，而且很可能将继续停留在我们解决问题的能力所及的边界之外。
实际上，只有120条路线是必须检查的，因为我们将哪座城市选作起点无关紧要。换句话说，对于n座城市，只有（n–1）！条可能的路线。
有一家互联网公司曾经想用这个庞大的数字给公司起名。传说他们把这个单词拼错了。可惜他们没有让谷歌（Google）检查拼写。
我们对NP的确切定义有点含糊其词了。给出真正的定义会让我们有点离题太远。然而NP问题的大部分例子实际上都是2n或n!的。很重要的一点是，NP不代表“非多项式”（NonPolynomial）。它代表的是“非确定性多项式”（Nondeterministic Polynomial）。它的意思是，如果由一台非确定性机执行任务，这些问题可以在多项式时间内解决。非确定性机的本质是一台同时进行许多次猜测的机器。哎，非确定性机并不存在，我们无法使用非确定性机解决我们的问题。
我们将在第7章第2节深入探讨这些概念。
没有窍门的计算方法
在上一节，我们遇到了一些问题，它们唯一已知的算法是穷举搜索，这种算法需要花费太多时间才能完成。到目前为止，没有人知道能够解决其中任何一个问题的多项式算法。也就是说，还没有人发现能够在更短的时间内解决这些问题的方案。在这一节中，我们将会了解，为什么大多数研究者都相信不存在这样的多项式算法。
如果你花一点时间研究集合划分问题和子集和问题，你会发现它们是非常相似的，而且实际上是相关的。我们可以轻易地将集合划分问题的例子转变成子集和问题的例子。因为在集合划分问题中，你其实是在寻找各元素构成的一个子集，令它们的和等于该集合所有元素之和的一半。例如，思考集合{12,63,13,82,42,54,24,76,22}。判断该集合是否可以划分成两个集合并令其元素之和相等的一种方法是查看它是否存在一个子集，令其元素之和等于该集合所有元素之和的一半。既然如此，我们就必须判断是否存在一个子集令其元素之和等于
C=（12+63+13+82+42+54+24+76+22）/2=388/2=194。
如果存在这样的子集，那么该集合的元素可以划分成两部分，一部分在该子集中，一部分不在该子集中。如果不存在任何子集的元素之和等于194，那么该集合的划分问题的答案就是否定的。
我们在这里要说的是，如果我们能解决子集和问题，那么我们就几乎肯定解决了集合划分问题。用我们的符号体系表示：
解决子集和问题⇒解决集合划分问题。
如果你有一个集合划分问题的例子，只需要将这个问题转换成子集和问题，就像我们在上面做的那样，将C设置成该集合所有元素之和的一半。如果你能解决第一个问题，那么你就一定能解决第二个问题，这种说法意味着第一个问题的难度相当于或大于第二个问题。所以我们指出了子集和问题与集合划分问题一样难或者比后者更难。换句话说，集合划分问题与子集和问题一样难，或者比后者更容易。我们将这种关系写成如下这样：
集合划分问题≤P子集和问题。
让我们总结一下我们刚刚对任意两个判定问题做了些什么。假设我们有一个问题B，这个问题是计算机可以解决的。这意味着我们有这样一台机器，向其中输入该问题的一个例子，它就会根据解决方案输出“是”或“否”的答案。我们可以用图5.11表示这一过程。输入从左边进入机器，机器计算之后，输出“是”或“否”的结果。
图5.11 判断问题B的机器
现在想象我们有一个问题A。如果有一种方式可以将问题A的例子转换成问题B的例子，我们就可以制造一种机器，通过将转换器连接到问题B的方式来判断问题A，如图5.12所示。
问题A的一个例子从左边输入。这个例子被转换成问题B的一个例子，然后进入问题B判断机，对两个问题给出一个答案。
我们不想让转换器随意地将问题A的例子转换成问题B的例子。我们需要这些例子有相同的答案。换句话说，我们必须要求转换器在输入答案为“是”的问题A时，必须输出答案同样为“是”的问题B。如果问题A的输入从问题A判断机那里得到的答案是“否”，那么转换器应该输出答案为“否”的例子。我们做出进一步的要求：转换器应该在多项式次数的操作步骤下完成它的任务。你很快就会明白这种规定的必要性。
图5.12 通过使用问题B判断机来判断问题A的机器
当我们在问题A和问题B之间拥有这样的关系时，我们说我们有“问题A到问题B的归约”或“问题A归约到问题B”。
让我们看看一个问题归约到另一个问题的又一个例子。哈密顿回路问题可归约到旅行推销员问题。思考图5.10中的哈密顿回路问题的例子。我们将它们转换成图5.13中旅行推销员问题的例子。别忘了旅行推销员问题需要完整的加权图形。我们在原本不相连的点之间连线成边，使图形完整。为了区分不同类型的边，我们将新的边画成灰色。
至于权重，我们设所有黑边的权重为0，所有灰边的权重为1。接下来的步骤会将它转化成为旅行推销员问题的例子：我们将所需整数K设置为0。如果存在某条旅行推销员回路的权重（小于或）等于0，也就是说该回路没有使用任何一条新的灰边，那么最初的图形就存在哈密顿回路。图5.13左边的图像含有这样一条旅行推销员回路，而右边的图像没有。我们成功地将哈密顿回路问题归约到旅行推销员问题。
图5.13 哈密顿回路问题的例子转换成旅行推销员问题的例子
知道某个困难的问题能否归约到另一个问题为什么能够帮到我们呢？毕竟这两个问题对于任意较大的数字n而言都是无法解决的。在接下来的几页里，我们将见到许多原因，它们将解释这种归约理念为什么是整个研究领域的重大基础。
让我们稍微思考一下这种情况。假设NP问题A可以归约到NP问题B，也就是问题A≤P问题B。现在设想一下，某个超级天才突然横空出世，提出了某种神奇的最新算法，可以在多项式时间内解决问题B。毫无疑问，这个超级天才会因为最终发现解决问题B的容易方法而赢得许多赞誉。用指数算法解决问题B需要许多万亿个世纪，而使用新的多项式算法，几分钟之内就能得到答案。
但是并不仅限于此。使用多项式归约的方法，不仅会让这名超级天才因为解决问题B而名声大噪，而且问题A也将在多项式时间内得到解决。要想在多项式时间内解决问题A，只需要通过多项式转换器将问题A的例子变成问题B的例子，然后将这个例子应用到这名超级天才新提出的多项式算法中去。由于转换过程只会花费多项式时间，新算法也会在多项式时间内完成，所以整个过程可以在一个多项式时间加一个多项式时间内完成。两个多项式相加是一个多项式，所以整个过程可以在一个相对短的时间内完成。所以我们的超级天才不但可以解决问题B，也可以解决能够归约到问题B的任何其他问题。
为了理解两个互相关联的问题之间的关系，让我们用攀登两座山来进行类比。由于珠穆朗玛峰比麦金利山高，所以下列命题为真：
如果你能登上珠穆朗玛峰，那么你一定能登上麦金利山。
这意味着登上珠穆朗玛峰比登上麦金利山更难。这相当于说：
如果你不能登上麦金利山，那么你肯定不能登上珠穆朗玛峰。
类似地，当问题A到问题B存在多项式归约的关系时，下列命题为真：
如果问题B可以在多项式时间内解决，那么问题A也可以在多项式时间内解决。
这意味着问题B比问题A难或者和问题A一样难。这个命题等同于：
如果问题A不能在多项式时间内解决，那么问题B也不能在多项式时间内解决。
到目前为止，我们已经讨论了这样一种NP问题：另一个NP问题可归约到这种NP问题。现在让我们讨论另外一种NP问题：每一个NP问题都可归约到这种NP问题。每个NP问题都可归约到的这种NP问题称为NP完全（NP-Complete）问题。在某种意义上，NP完全问题是最难的NP问题。实际上，在第2节中介绍的所有5个问题都是NP完全问题，而且是可彼此归约的。
由于任何其他NP问题都可归约到NP完全问题，所以如果有任何一个NP完全问题可以在多项式时间内解决，那么所有NP问题就都可以在多项式时间内解决。
建立了NP完全问题的观念之后，就可以看出为什么研究者们认为解决这些问题的多项式算法永远不可能存在了。以任意NP完全问题为例，比如旅行推销员问题。许多年来，人们徒劳无功地寻找解决这个问题的多项式算法。本节已经阐述了NP完全问题之间的内在联系。如果任何人发现了能够解决任何NP完全问题的多项式算法，那么旅行推销员问题也会有多项式解决方案。从某种意义上说，任何NP完全问题的研究者同时也在研究旅行推销员问题。所以我们可以说，有几千人多年以来一直在为我们的问题寻找多项式算法，但全都徒劳无功。似乎不存在这样的算法。
为什么指出某个问题是NP完全问题是件重要的事？通常有两个至关重要的原因。首先，通过指出某个问题是NP完全问题，我们就是在论证为这个问题找到有效算法的难度等于为其他NP完全问题找到这样的算法。既然没有人能够为任何NP完全问题找到有效算法，我们就是在指出这个问题固有的难度。如果你得到一份工作，内容是为解决某个问题写出漂亮的多项式算法，结果你很难完成这项任务的话，你的老板就会找你的麻烦。然而，如果你指出这个问题是NP完全问题，你可以争辩说不只是你不能找到好的算法，事实上没有人能找到。这样的说辞可以保住你的工作。
NP完全问题之所以重要的另一个原因是，一旦知道某个问题无法轻易解决，我们就可以放开手脚，寻找有助于我们找到该问题近似解决方案的其他算法。第4节介绍了能够在合理时间内找到近似解决方案的算法。
当你有一个NP完全问题时，找到其他NP完全问题并不困难。如果已知A是一个NP完全问题，想证明B也是NP完全问题的话，只需要完成下面两个任务：
1.证明B是NP问题。
2.证明A≤PB——B的难度等于或大于A。
已知A是NP完全问题，因此所有NP问题都可归约到A，而A可归约到B，所以我们知道所有NP问题都可归约到B。该过程可见于图5.14，我们在有归约关系的问题之间画上箭头表示。
图5.14 从一个NP完全问题到另一个NP完全问题
再重复一遍重点：一旦我们拥有一个NP完全问题，我们就能轻易找到其他NP完全问题。但是如何找到第一个NP完全问题呢？20世纪70年代初，北美研究者斯蒂芬·库克（Stephen Cook）和俄罗斯研究者雷奥尼·莱文（Leonid Levin）各自独立证明了可满足性问题是NP完全问题。该定理后来被称为库克–莱文定理（Cook-Levin theorem），是计算机科学中最令人赞叹的定理之一。该定理声称所有NP问题都可以归约到可满足性问题。我们已经见到了5个不同的NP问题。目前人们已知的NP完全问题有数千个之多，分别与图形、数字、DNA测序、调度任务及其他各种领域有关。这些问题有许多不同的表象和形式，但它们全部都能归约到可满足性问题。但是不止于此！库克和莱文没有证明如今已知的每个NP问题都可归约到可满足性问题；他们指出的是，所有NP问题——甚至包括那些还没有被描述的——都可归约到可满足性问题。
库克和莱文证明可满足性问题是NP完全问题的方法非常聪明，值得我们了解。作为第一步，他们首先关注了所有NP问题的共同点。根据定义，每个NP问题都可以被一台计算机在至多指数或阶乘次数的操作中解决。现在看看这样一台计算机是如何工作的。计算机的内核是什么？答案很简单：计算机和它们的芯片遵循逻辑规则。在每台计算机中都有数十亿个逻辑开关，执行与、或、否、蕴涵这样的逻辑运算。所以既然每个NP问题都可以用遵循逻辑规则的计算机解决，那么每个NP问题都可以归约到可满足性问题。我们在本章开头就讨论了计算机是逻辑和理性的机器。现在我们清楚地看到了这一点。每个计算机问题都可以用逻辑语言表达出来。
在结束本节之前，让我来告诉你们如何挣到100万美元。为了促进数学的发展，克雷数学研究所（Clay Institute）在千禧年之际公布了数学的七大难题，它们都是各自领域最重要且最难的问题。任何人只要能够解决这些“千年难题”中的任何一个，都能获得100万美元。其中一个问题是P=？NP问题，即“P等于NP吗？”我们在第2节的结尾看到，P是NP的子集，也就是说，每个容易的问题可以在比大量时间更少的时间内解决。但是我们可以问出相反的问题：NP是P的子集吗？每个困难的NP问题是否有可能在多项式时间内解决？如果NP是P的子集，那么P=NP。
如果NP不是P的子集，那么NP中存在不属于P的问题，P≠NP。图5.15描述了这两种可能性。要想获得大奖，你只需要证明其中一个答案是对的。
图5.15 P与NP问题的两种可能
要将这笔奖金收入囊中，你该如何开始呢？有两个可能的方向。你可以尝试证明P=NP，也可以致力于指出P≠NP。想要指出P=NP，你需要做的全部事情就是拿出一个你最喜欢的NP完全问题，然后找到解决它的多项式算法。正如我们所见，如果你真的发现了这样的算法，那么所有NP问题都将可以在多项式次数的操作下解决。一个需要指数或阶乘次数操作才能解决的问题也能在多项式次数操作下解决，这样的想法似乎有些奇怪。然而，我们在欧拉回路问题上见到过类似的情况。我们可以不用查看所有n!种可能的回路来判断是否存在欧拉回路，只需要检查与每个点相连的边是否为偶数就可以了。对哈密顿回路问题而言，存在类似的窍门吗？许多年来，那些最聪明的人一直在寻找这样的窍门或算法，至今无人成功。不过或许你拥有他们缺少的某种更深的见解。快去发现它吧！
另一方面，你可以试着指出P≠NP。要想实现这一点，有一种方法是拿出一个NP问题，证明它不存在多项式算法。这样的假设很难证明：还有很多很多算法没有被人发现。它是数学领域最难的问题之一。作为最后的线索，我应该提醒一句，大多数研究者都相信P≠NP。
从本质上说，库克和莱文做的事情就是指出，对于每个NP问题和这些问题的每个输入，都可以模仿计算机寻找解决方案时的行为，写下一串（极长的）逻辑表达式。如果计算机可以找到解决方案，那么这个逻辑表达式就是可满足的。如果不能找到解决方案，这个逻辑表达式就无法满足。
有人相信这些命题中的任何一个都无法被现代数学的公理证明。他们相信P=?NP问题“独立于”数学公理。我在第4章第4节中讨论了这样的独立状态，并将在第9章第5节中再次讨论。
我感觉有责任警示你们，七大千年难题之一庞加莱猜想（Poincaré conjecture）已经被格里戈里·佩雷尔曼（Grigori Perelman）解决了。所以现在解决剩余的难题就更紧迫了。抓紧时间！
找不到的精确结果
这些NP完全问题不是计算机科学家和数学家创造出来的抽象概念。它们来自现实世界的应用场景，是需要解决的真实问题。工业和计算机专业人士一直在寻找这些问题的有效解决方案。为这些问题的答案等待几个世纪是不可接受的选项。
为了应对这些问题，计算机科学家们发明了能够消除困难问题某些痛点的算法。这样的算法称为“近似算法”（approximation algorithms）。这些算法只需要多项式次数的操作，但并不总是能给出正确的答案。它们距离正确答案有时差之毫厘，有时谬以千里。
近似算法通常是启发式的（heuristics）。它通过经验学习并给出建议，这种基于经验的法则不会100%正确，但“足够接近”解决方案。
旅行推销员问题大概是第2节中提到的所有NP完全问题中最容易凭直觉想象的一个。让我们回顾这一节开头介绍的这个关于大城市的问题吧。假设推销员从洛杉矶出发。出发的时候他没有考虑自己要走的整条路线的长度；相反，他只是寻找在清单中离自己最近的城市。离洛杉矶最近的城市是旧金山。当他抵达旧金山，他再次寻找自己还没有去的距离最近的城市：丹佛。当他到达每座城市的时候，他的下一个目的地都是他还没有去的距离最近的城市。这是处理该问题的一种非常符合直觉的方式。旅行者不看“全局”，他只是贪婪地寻找最近的城市。这种方法称为“最近邻点法”（nearest neighbor heuristic）。在每一点时，只需前往相邻的最近点即可。这种算法总是能在多项式时间内完成。然而它并不总能找到正确的解决方案。
虽然最近邻点法似乎总能找到正确的解决方案，但它实际上不能，而且很容易看出为什么。思考图5.16中的完整加权图。图中只给出了相邻两点之间的加权边长，不过其他加权边长可以根据它们算出来。
图5.16 最近邻点法的一个反例
假设我们强迫旅行者从a点出发。她的下一个目的地会是仅1英里之遥的b点。从b点出发，旅行者将面临两个选择：4英里之外的c点或3英里之外的e点。根据我们的算法，她必须选择e。遵循最近邻点法，这位旅行者必须采取以下回路的路线：
a→b→e→c→f→d→a。
我们这位可怜的旅人必须旅行1+3+7+15+31+21=78公里。
随着心智的成熟，我们了解到在生活中处处抄近道并不总是能让你在最短的时间到达自己想去的地方。有时候捷径会让你偏离目标。思考下面这个不遵循最近邻点法的回路：
a→b→c→d→f→e→a。
这个回路将需要
1+4+16+31+8+2=62英里。
很显然，最近邻点法并不十分适用于这个完整加权图。
集合划分问题又如何呢？这里有一种多项式近似算法，我称之为两极配对法（extreme pairs）。假设存在一个由数字元素构成的集合{24,68,61,41,35,51,58,39,4954,29,23}，将它的元素按下面的方式排序：
23,24,29,35,39,41,49,51,54,58,61,68。
将位于两极的最小和最大元素（23和68）选出来划到一边。接着将余下的最小和最大元素（24和61）划分到另一边。按照这种方法继续划分，直到每个元素都被放到两边中的一边。我们会得到左边的元素相加等于268，而右边的元素相加等于264。这是更好的解决方案吗？
我们值得花几分钟时间看看为什么两极配对能够奏效。将这些数字按顺序排列，如图5.17所示。
图5.17 两极配对之和几乎相等
第一个数字和最后一个数字的和是91。第二个数字和倒数第二个数字是85。这两个数字不一样，但它们足够接近。按照同样的方式继续下去，我们还会得到更多数值相近的和。这种近似算法所做的就是将这些相近的和分配到不同的两边。它或许不是最佳解决方案，但它要好过等待400万亿个世纪。
每次有新的NP完全问题出现的时候，人们就会寻找有助于解决这个问题的优秀近似算法。正如我们所言，NP问题无处不在，而且非常重要。各行各业必须找到应对此类问题的办法。近似算法不仅仅只是被构想和描述出来，它们还会被拿来比较和分析。哪种启发式算法更好？哪种算法能让你更接近不可获得的真正答案？哪种算法的工作速度更快？哪种算法能够在输入更大时得到正确的答案？还有许多工作等待完成。
由于旅行者不准经过任何城市两次，我们必须假设她在从点c向点e的旅程中坐飞机飞越了点a。
我从未在文献中见过这种近似算法。这大概是因为它一般很难得到比较好的解决方案。
存不下的运算过程
NP并不是故事的终点。有些问题的算法甚至需要比2n和n!更多的操作次数。有些问题（不是很容易被描述出来）需要次操作，它们叫作超指数问题（superexponential problems）。与其花时间讨论这些问题的内容，不如让我们看看这个函数有多大。对于n=10这样很小的输入，指数是210=1024。使用1024作为指数，我们会得到21024，它比任何可想象的数字都大。
有一些同样疯狂的函数，如
（n!）!或。
将n取一些较小的数值，试着运算一下。
到目前为止，我们关注的是一台计算机需要完成多少次操作才能解决一个问题。操作次数和解决问题所需时间的多少是成比例的。然而还存在衡量问题难度的其他方法。要想解决更难的问题，不仅需要很多时间，还需要很多内存空间。当计算机解决某个问题时，它要使用内存来存储部分运算。需要存储运算的空间越大，问题就越难。
和之前一样，每种算法都有一种与之关联的函数，该函数描述了解决该问题所需内存空间的大小。函数越大，需要的空间越大，问题也就越难。
存在这样一类有趣的问题，它们需要的内存空间可以用多项式函数表示。这类问题表示为PSPACE。目前已知NP问题——可以在指数或阶乘时间内解决的问题——可以在多项式空间中解决。换句话说，NP是PSPACE的子集。
有很多问题都属于PSPACE，而且其中的一些和博弈游戏有关。有些双方博弈游戏存在制胜策略，也就是说，有些方式一定能让某个特定的选手获胜。思考井字棋游戏。已知先落子的一方可采取一种策略，一定能取得平局或胜利。现在考虑井字棋的广义情况，将3×3的棋盘换成n×n的棋盘。对于这样的博弈，是否还存在某个选手的制胜策略呢？答案可能取决于n。判断某个n×n博弈中是否存在制胜策略就是PSPACE中的一个问题。其他类型的广义博弈游戏如国际象棋、西洋跳棋、四子连珠、余子棋（nim）、围棋等也已知属于PSPACE。
综上所述，从容易的到非常难的，计算机问题有许多种不同的类型。这些问题的种类可以用图5.18表示。
图5.18 可解决问题的层级
这张图属于一张更