旅行商问题中P等于NP吗？

前两年国内有一部热播的电视剧《天才基本法》，它反复提到了“P=NP”问题。这可是一个计算数学领域天大的难题，它耗费了无数科学家的大量时间和精力，迄今也未能解决。这个问题的重要性好比物理学中的大统一理论、数学中的哥德巴赫猜想，是皇冠上的明珠，是无数科学家梦寐以求的目标。毫不客气地说，如果有人能够解决这个问题，那么这个人将一举成名，同时这个成就也将是数学界近百年最伟大的发现。旅行商问题，就和P=NP问题相关。我们回到宝洁公司悬赏的这33个城市的最短路线问题。先说一个好消息，早在1954年，美国加州的兰德公司的三位数学家，乔治·丹齐格（George Dantzig）、雷·富尔克森（Ray Fulkerson），以及塞尔默·约翰逊（Selmer Johnson），提出了一个基于线性规划的方法，通过手工计算，用了几星期时间就得到了环游美国48座城市的最短路线。

很显然，这三位数学家解决的这个48个城市的路线问题，比宝洁公司的33个城市的路线问题难得多，所以宝洁公司的这个问题其实已经被解决了。不过先别高兴得太早，尽管这三位数学家解决了环游美国48个城市的难题，但是我们不能说旅行商问题已经被解决了。关键在于问题的规模。如果城市的数量再大一些，这些数学家提出的算法所需要的时间，可能又将是一个天文数字。也就是说，针对更多城市的旅行商问题，这些数学家并没有找到通用的，足够好的算法。你看到这里，肯定脑子里有一个疑问：什么叫做“好”的算法？直觉上，好的算法就是能够在比较短的时间内找到问题答案的算法。但是要知道，绝大多数情况下，算法找到问题答案的时间，都会和问题的规模有关系。

对于旅行商问题而言，找到48个城市的最短路线，显然要比33个城市的难度高得多，因此哪怕我们再苛刻，也不能要求一个算法对于任意不同规模的旅行商问题，都能在某个固定时间（比如一分钟）内找到答案。

所以我们一定得允许在城市数量增加时，算法的求解时间相应增加。好算法和坏算法的关键，就在于增加的快慢。好的算法，这个求解时间随着城市数量增加不能太快。那么什么叫快，什么叫慢呢？数学家有一个定义，只要一个算法找到答案所需要的时间，能做到n^k可以了。这里的n就是问题的规模。

对于旅行商问题，n就是城市的数量。指数k可以是任意值，例如取2、3或者更大的数，但必须是固定的，不能随着n的增加而增加。例如，如果算法的时间是n^3，那么这个算法就是好的。n^k 是n的多项式，因此满足这个条件的算法，叫做多项式时间算法。多项式时间算法是一个好算法。如果一个算法所需要的时间和规模的关系是k^n ，例如2^n、3^n等这样的指数函数形式，那么这些算法是一个“坏”的算法。当然，比指数函数更慢的，还包括之前提到的n的阶乘，阶乘级的算法也不是好算法。

我们举个例子来说明一下好算法和坏算法的差距。假设一个算法是多项式时间算法，所需要的时间和规模的关系是n^3，另外一个算法是指数时间算法，关系是2^n。为了看得更清楚，我们拿一台每秒钟能够进行109 次计算的计算机，看看这个计算机运行这两个算法所花费的具体时间的差别。当n小于10的时候，指数时间算法所需要的时间更短，但当n超过10以后，指数时间算法花费的时间就会超过多项式时间算法，并且随着n的增大，这个差距越大。具体来说，当n=25时，第一个算法需要0.02毫秒，而第二个算法则需要0.03秒。这个还差距不大。当问题规模n到了50的时候，多项式时间算法所需要的时间增加到了0.1毫秒，增加得不多。但指数时间算法的时间，从0.03秒，一下子达到了13天。而如果n增加到100的时候，多项式时间算法的耗时增加到了1毫秒，但是指数时间算法增加到了40万亿年。这就是为什么指数时间算法被称为“坏的算法”，因为当问题规模比较大的时候，算法需要的时间就变得不可接受了。

因而，在计算机算法领域，我们有一个最基本的假设：所有实用的、快速的、高效的算法，所需要的计算量，和问题规模的关系，都应该是多项式级别的。你可能会问，如果n比较小，那么指数时间算法的耗时，可能会比多项式时间算法更短啊。没错，但是计算机的发明就是为了处理大规模数据的。所以科学家在比较算法快慢的时候，就是比较在问题规模比较大的时候的表现。算法可以明确地分为好算法和坏算法的这种思想，彻底改变了计算数学。从此大家都有了明确的目标，为了一个问题找到好的算法，并且不断提高算法效率。然而，对于旅行商问题，尽管数学家们一直在前赴后继地改进算法效率，但是一直没能找到多项式时间的算法。于是，很多数学家就产生了一个想法：是不是旅行商问题，从理论上就不存在好的算法呢？

当时的几个数学家也说过这样的话：比如，杰克·埃德蒙兹在1967年说：“依我猜想，旅行商问题没有好的算法。”梅里尔·弗拉德在1956年说：“要想成功解决该问题，很可能需要另辟蹊径，使用前所未有的新方法。事实上，该问题的通用解法很可能压根不存在，若能证实这个结论也是很有价值的。”理查德·卡普在1972年说：“我们在本文中给出了一些定理。它们有力地显示（尽管不足以证明）：该问题像许多别的问题一样，也将是一道永恒的难题。”我们可以看出，数学家们在思考问题时的思路和角度，和普通人是不同的。

为了看清这一点，我先来问你一个问题。当你拿到一道数学题的时候，你应该干什么？多数人会认为：当然应该着手找这个问题的解法。

而对于这个问题的难度，我们大部分人是不会主动去研究的。因为在我们眼中，问题到底难不难和你有没有找到好的解法有着密切关系。也就是我们常听说的这句话：难者不会，会者不难。而数学家的反应可能会出乎你的意料。他们拿到一道题之后，不是首先去找这个问题的解法，而是首先会去研究一下这个问题本身的难度。而且“难者不会，会者不难”在他们眼中是不成立的，问题的难度和解决方法没有直接关系。

举个很形象的例子。你毕业去了一家高科技公司，上级丢给你一个和企业生产相关的数学问题，找你要这个问题的解法。你研究了几天，也找不到一个好的解法，然后你只能愁眉苦脸地对上级说，这个问题你没找到答案。但如果上级把这个问题丢给一个数学家，虽然最后他也没能找到这个问题的解法，但是与你不同的是，他会拿着一堆数学证明，理直气壮地去和上级说：“领导，虽然我没能做出这道题，但是这不是我的问题。因为我从理论上证明了，这个问题本质太难了，不光我做不出来，世界上任何人都做不出来。”这就是理论的价值。所以，数学家们对问题本身的难度感兴趣。他们想知道，哪些问题从理论上存在好的算法，哪些问题从理论上就不存在好的算法。数学家们，把理论上存在好算法的问题叫做P问题。这里的P是多项式时间（polynomial-time）的意思，也就是我们可以找到一个算法，它解决该问题的时间是问题规模的多项式函数，也就是前面提到的nk的含义。

什么样的问题存在好的算法呢？排序问题就有好的算法。排序就是把一组数按照从大到小顺序排列。对于一个长度为n的数组，数学家们已经证明了，最快的排序算法所需要的时间，是n×log n。这是一个多项式时间的算法。我们平常在打牌的时候通常会一边抓牌一边按照大小把牌的顺序排好。绝大部分人都不会觉得这是一个难题。这是因为排序问题的本质很简单。除了排序问题，还有很多问题，包括在序列中查找某个数、判断一个数是否为质数等问题都属于P问题。我们能够用多项式时间算法来解决这些问题，因此当这些问题的规模增大的时候，这些算法的耗时不会出现爆炸式增长。但是对于我们刚才的旅行商问题，是否属于P问题呢？

很遗憾，我们不知道答案。不知道答案的意思是，有可能属于P问题，也有可能不属于P问题。为此，科学家们发明了一个词，叫做NP问题。这里的NP，不是非多项式（not polynomial），而是非确定性多项式（non-deterministic polynomial），也就是这些问题，我们“不确定是否能用多项式时间解决”。NP问题有两个特点，第一就是找到答案很难，换句话说，我们还没能找到一个多项式时间解决该问题的算法。NP问题的第二个特点是，问题的验证比较容易。关于这一点会涉及一些数学概念，我们不深入介绍。拿旅行商问题来说，虽然让我们找一条长度短于100英里的路线不容易，但是只要别人给我们一条路径，我们就可以很快地验证它是否满足这个要求。

这个给我们带来了一点希望，因为如果连验证答案都很难，那么我们可以想象，在多项式时间内找到这个问题的解，就非常渺茫了。通俗地来说，解决很难但验证很快的问题就是NP问题，旅行商问题就是NP问题。而且数学家们已经提出了一些严格的方法，可以从理论上证明某些问题属于NP问题。看到这里，你应该可以意识到关键所在了：NP问题，有没有可能和P问题是同一类问题？这就是P是否等于NP。P是否等于NP，换句话来说，就是是否“所有可以轻松验证的问题也可以轻松解决”？

支持P=NP的科学家，认为存在某一种方法，可以将NP问题转化为P问题，只是我们现在暂时还没有找到这个方法。而持相反态度的科学家认为，NP问题和P问题不是一类问题，我们永远无法在多项式时间内解决NP问题。假设P=NP是真的，那么我们首先要注意的，就是当前的加密系统。因为加密系统的核心原理，就是把一个很大的整数分解成为两个质数的乘积。这个问题是NP问题，迄今没有效率很高的解法。但如果P=NP，这意味着存在高效的算法进行质因数分解，意味着现有加密体系从本质上已经不安全了。当然，P=NP可能给我们带来更多的好处。规模再大的旅行商问题都能很快找到最短的路线，工厂能达到最大的生产能力，航班也能安排得当、避免延误，因为这些资源分配问题、规划问题大部分都是NP问题。由此科学界、经济界、工程界将会出现更加强大的工具和方法，重大突破源源不断。

当前的大部分科学家认为P不等于NP，但是也没有人能用理论证明这一点。美国计算机科学家、1985年图灵奖获得者理查德·卡普（Richard Karp）也认为P不等于NP。他说：“我认为传统的证明方法是远远不够的，解决这个问题需要一种绝对新奇的手段。直觉告诉我，这个问题最终会由一位不被传统思想束缚的年轻科学家解决掉。”尽管这个问题还没能解决，但是数学家们前赴后继地在旅行商问题上投入，也提出了很多算法。很多在旅行商问题上的算法，对运筹学和优化理论产生了深远的影响。