前兩年國內有一部熱播的電視劇《天才基本法》，它反復提到了“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。他說：“我認為傳統的證明方法是遠遠不夠的，解決這個問題需要一種絕對新奇的手段。直覺告訴我，這個問題最終會由一位不被傳統思想束縛的年輕科學家解決掉。”盡管這個問題還沒能解決，但是數學家們前赴后繼地在旅行商問題上投入，也提出了很多算法。很多在旅行商問題上的算法，對運籌學和優化理論產生了深遠的影響。