1701018127
我们来看那位售货员的行走路线。如果他要走访20位顾客一次且仅一次，不同的路线可以如下产生。首先，第一站有20种选择。然后，第二站有19种选择，如此继续选择，可知最后给出的不同的路线会有20！种。由于某条由首站到末站的路线和由末站经历同样中间站再回到首站的路线实际上是同一条路线，所以要除以2，即
1701018128
1701018129
1701018130
1701018131
1701018132
1701018133
为了选取最短的路线，一个笨办法是将这些路线的长短两两作比较，因此一共要比较次，才能找出最短路线。由于这个算法太笨，以每秒进行1 000亿次运算的计算机求解，则需要4个半月。这样一个看似简单的问题，如果需要花费几个月甚至更多时间才能计算出结果，实际上是行不通的。
1701018134
1701018135
为了讨论方便起见，我们假定计算机的存贮量足够大，运算时间任意长，计算精度也足够保证问题的要求，这样“理想”的计算机称为图灵机（Turing Machine）。在图灵机上解题，计算时间的长短主要与以下因素有关：
1701018136
1701018137
（1）计算机的速度；
1701018138
1701018139
（2）实际问题规模的大小；
1701018140
1701018141
（3）算法的选择。
1701018142
1701018143
如果研究的问题，其规模n是确定的，此时解题所需的时间主要与计算机的速度和选择的算法有关。
1701018144
1701018145
以fA （D，n）表示用算法A求解规模为n的问题所需的运算次数。要缩短运算时间或在一定时间内能解更大规模的问题，其主要办法为：提高计算机的速度和改进算法，减少运算次数。
1701018146
1701018147
首先考虑前者的影响。如果现有的计算机每小时解题的规模为n，则用了快100倍、1 000倍的新计算机后，一小时所能解决问题的规模会如何变化？请看表8.4.1。
1701018148
1701018149
表8.4.1 计算机速度与解题规模之间的关系
1701018150
1701018151
1701018152
1701018153
1701018154
从上述表格中，可以看出：算法复杂性为规模n的多项式时，计算机成倍提速后，相应地解题规模也成倍增长；对算法复杂性为指数函数的算法，例如当f A （D，n）=3n时，计算机提速1 000倍后，解题规模n只能增加6.29。所以，对指数函数的算法，单纯靠计算机提速来增加解题的规模n，收效甚微。因此转向算法的研究是必要的。
1701018155
1701018156
首先对算法进行分类：如果存在多项式P（n）和正整数n0，使得当n＞n0时，恒有fA （D，n）＜P（n），则称A为解决问题D的多项式算法，又称为有效算法，或好算法。如果fA （D，n）是n的指数函数，则称算法A为解决问题D的指数型算法，又称为“坏”算法或“无效”算法。例如，求解旅行售货员问题就是指数型算法。
1701018157
1701018158
对于一个算法复杂性为n80的问题，虽然是多项式算法，但实际上也是不可接受的。因为280≈1024是一个“天文”数字，在现实情况下几乎不可能算出结果。幸运的是，一个实际问题一旦找到多项式算法，经过一系列的改进，其算法复杂性一般会降到n的三次多项式，甚至更低。因此有理由相信，多项式算法总是有效的。
1701018159
1701018160
我们定义的算法复杂性是考虑所有可能情况下，算法的运算次数。而实际上，有些算法只是在“最坏的情况”下才呈现指数型的增长，在一般情况下则很有效，因此仍然被人们广泛采用。例如，求解线性规划通常使用单纯形法，在一般情况下的平均运算次数是规模n的多项式，速度很快，但已经证明它在“罕见”的情况下是一个指数型的算法。
1701018161
1701018162
大多数的指数型算法，只是穷举搜索法的变种。只有对问题的结构充分了解后，才有可能给出多项式算法。解决实际问题时，当然要寻求多项式算法。但如果一个问题已经被证明没有多项式算法，再寻找精力就白费了，因此有必要对实际问题进行分类。
1701018163
1701018164
P问题和NP问题 对于一个实际问题，如果其存在多项式算法，则称为P问题（polynomial problem）。对P问题研究的中心问题是如何改进现有的计算方法使运算次数更少。如果已经证明不存在多项式算法，则我们认为这一个问题是难问题。对于难问题，一般只能寻找可以接受的近似算法。
1701018165
1701018166
还有一类实际问题，称为判定问题；是能用“是”（有）或“不”（无）来回答的问题。例如，问用2 500元能够购置29英寸的彩色电视机吗？回答这个问题“能”时，不必知道当前市场上29英寸彩电的最低价，只需了解确有价格不超过2 500元的29英寸彩电出售即可。对于一个判定问题，如果对所有回答为“是”的实例，都存在多项式算法来验证它的正确性，则称此判定问题为NP问题（不确定多项式问题，non-deterministic polynomial problem）。显然P问题一定是NP问题。
1701018167
1701018168
1971年，美国计算机科学家库克（Stephen Cook，1939—）发表了一篇十分著名的论文《The Complexity of Theorem-Proving，Association of Computing Machinery》。他首先指出，NP问题中存在一类称为NPC问题（完备问题，non-deterministic polynomial complete problem）。这类问题有如下特性：
1701018169
1701018170
（1）类中每一个问题至今尚未找到多项式算法；
1701018171
1701018172
（2）如果类中任一个问题有多项式算法，那么该类中其他问题都有多项式算法（即这类中的任意两个问题都存在多项式算法相互转化）。
1701018173
1701018174
到目前为止，NPC问题已被扩充为近千个，其中包括旅行售货员问题。许多优秀的数学家、理论计算科学家在过去几十年来，试图寻找它们的多项式算法都没有成功。这越来越使人们相信，对它们也许根本不存在多项式算法。然而要证明这一猜想，既是有重大意义的，又是十分困难的。2000年5月24日Clay数学所宣布七个“千禧年数学难题”，每一个悬赏一百万美元征解，其中的第一个问题就是这个猜想。这个猜想的解决实属渺茫，有理由相信，不提出一套全新的数学理论和方法，这个问题的答案是不会出现的。
1701018175
1701018176