個人演唱會還有

3680天

2000年5月，著名的克雷數學研究所提出了“世界七大數學難題”，其中的第一個問題便是NP完全問題，它所探討的是P=NP是否成立，那麼這個P=NP究竟是個什麼呢？今天我就試圖給你編出來。

P是否等於NP，對於21世紀的人類來說至關重要，因爲這個神祕的問題正處於計算機科學與數學的交匯處。事實上，P=NP問題是“計算複雜性理論”的一部分，它所討論的是計算機處理能力的極限。我們知道，計算機的工作必須依賴於算法，也就是一系列需要執行的命令。在完成某些任務時，計算機只需要幾微秒就可以實現，但另一些，以目前的計算機算法處理速度則可能需要幾十億個世紀。

由此可見，算法的效率就是一個至關重要的問題。比如說，計算機經常要做的一件事就是排序，有可能是按照字母表，也有可能是按照數字大小，有可能是升序，也有可能是降序。現在對5,3,4,2,1五個數字進行升序排序，對於我們人類來說，這太簡單的，你要是給幼兒園小孩兒出這道題，人家都會以爲你是在罵他，因爲我們人類知道應該以什麼順序排序，至於我們大腦怎麼運轉的，那就不知道，總是我們就是會。那麼讓一臺計算機來完成這個任務，它會怎麼辦呢？目前，一種常用的算法是“冒泡”排序法，這個算法的過程是，按照一種有規律的方式來考察相鄰的數對，如果其中一個大於另一個，要麼將它們交換爲所需的順序，要麼當它們處於正確順序時保持不動。

所以，對於5,3,4,2,1的升序排列，計算機就會這樣來做：首先比較5和3，發現5比3大，然後將二者調換位置。接着看第二個數對，發現5比4也大，於是又把5和4也交換順序，以此類推，結果經過這樣的四次比較後，5就成功地“冒泡”了，到達了它的正確位置，也就是序列的最末端。然後再從頭開始比較，首先是3和4，位置保持不變，然後是4和2。最後我們發現，只需經過10次比較，計算機就可以得到準確的數列。

對n數個進行排序也一樣，計算機也可以通過這一方法來完成任務，而且其所需的步驟數存在一個界限，這就是n的平方。像這樣的如果某個問題，可以在n的冪次步驟數內解決，就被稱爲可以在“多項式時間”內解決的問題，這就是P問題。這樣的算法就是高效率算法，計算機可以輕鬆地處理這些問題。

那麼什麼樣問題不存在高效率算法呢？最典型的就是“推銷員”問題。現在給定了城市數目和在不同城市間旅行所需要的不同費用，那麼推銷員能否找到一條最爲廉價的把所有城市都走遍的線路呢？答案是當然可以，因爲我們可以列舉出所有的線路，然後挨個比較一番就行了。但是這個方法並不是萬能的，三五個城市還好說，但如果是100個城市，那麼即便計算機的計算能力達到了每秒10億億次，用100的階乘除以10億億次，這種方法也還是需要大約4000個世紀，計算機能算，但推銷員他不能等啊。這個問題就不是在“多項式時間”內可以解決的問題，也就是說它不是P問題。

不過，推銷員問題雖然不是P問題，但卻是NP問題。所謂的NP問題是指，能夠在多項式時間內得到確認的一類問題。儘管我們很難找到銷售員問題的解，但是要通過計算來確認是否有比給定路線更爲廉價的路線，卻是非常快捷的。這兩者之間的難度差距是十分巨大的，找到銷售員問題的解，就好比是在一堆乾草中找到一根針，而找到一個比給定路線更爲便宜的路線，就好比拿出一根稻草或是那根針，然後問你是否找到了那根針。

可見，任何一個P問題必然也是一個NP問題，因爲在多項式時間內找到解，就是對它的確認。而目前亟待解決的問題是，是否任何一個NP問題也都是P問題呢？如果答案是肯定的，那麼P=NP就成立了。另一方面，如果我們找到一個NP問題，並且證明不可能存在對於它的高效算法，那麼P就不可能等於NP。

這就是流動銷售員問題具有重要地位的原因，它本身是一個很難的問題，而且所有其他NP問題都能夠轉化成它。如果我們能夠爲這一問題找到一種高效算法，就可以由此而推出P=NP。這個結果就意味着所有的NP問題都能高效地解決。

由此一來，我們便得出了一個推論，那就是我們有可能通過一種高效的計算機算法，找到一個大數的質因數。而現代密碼學所依賴的正是這個問題的難度，同時，它還爲電子商務的安全性與計算機網絡誠信提供了基礎。也就是說，如果P=NP，那麼黑客與密碼竊取者將在計算機世界中更加遊刃有餘。幸運的是，目前人們認爲機器不大可能以高效的方式解決所有的問題，所以至少現在來看，P還不等於NP。