真正的百萬答題——七大千年數學難題之「NP問題」
2000年5月24日，美國克雷數學研究所，發布了新世紀最重要的七大數學難題。並為每個問題的解決懸賞一百萬美元，答題時間沒有限制。與1900年初的希爾伯特之23問遙相呼應。
千禧年七大問題分別是：
P對NP問題， 霍奇猜想， 黎曼假設，楊－米爾斯理論存在性與質量缺口，納維-斯托克斯方程存在性與光滑性，BSD猜想。
這裡面只有NP問題是計算機界的重大問題，而且排名榜首，足見其在當今數學界重要地位！
要了解NP問題，我們首先要去理解一個概念：時間複雜度。
城市位置分布（出發地 合肥）
假如我要在假期從合肥開始自駕游，計劃遊覽完周邊，上海，南京，武漢，三個城市，然後再回到合肥來，為了節約時間，我肯定是傾向於總里程最少的線路。那麼我肯定要事先做好規劃，於是我把所有可能的方案全部都列出來：
4座城市之間距離
這裡總共有6種方案。
路線方案及里程
然後分別計算這些方案的總里程（不考慮實際道路情況）：
我們發現第 4種方案里程最短，於是我們選擇這個方案。
如果我的假期足夠長，不僅僅遊覽周圍3個城市，打算游遍華中10個城市呢？這種情況下，我該怎樣規劃最優的遊覽路線。用最笨的辦法，我們還是需要把所有可能的線路方案都列舉出來，於是以此類推，就有10！種方案，大約3628800種方案。到這裡，我們很快就發現，只要城市數目稍微大一點，採用窮舉的方法就變得幾乎不可行。因為，只要我們增加到第N個城市，可能的方案數目就會是原來方案數的N倍。所有我們能夠使用枚舉的N值實在是很小，稍大一點，計算量就會遠遠超過我們可以承受的水平。
指數爆炸的典型事件——麥粒和棋盤的故事
大家還記得那個在象棋盤上扔麥子的故事么？第一格放1粒麥子，第2格放2粒，。。。後面的麥子數目都是前一格的2倍，直到放滿64格為止。事實上，這個遊戲如果真的做到最後，那麼從地球上的第一顆麥粒，一直到現在所種出的麥子都不夠填上去。因為由於前後倍數的關係，數量很快就會急劇增大，人們給這樣極具增加的過程起了一個形象的名字，叫指數爆炸。而我們前面說的那個自駕游的增加速度遠比這個指數爆炸還要恐怖地多。所以為了衡量計算過程的複雜特性，我們引入了時間複雜度這個概念。這裡不是指的是計算需要的世界，而是說，隨著計算對象的增加，需要增加的計算量。
我們用這個O這個符號來記時間複雜度。棋盤麥粒問題的時間複雜度就是O(2n),前面的自駕游事件的複雜度就是O(n!)。這兩種事件的考慮對象一旦超過了某個限度，計算的次數都是任何機器都難以承受的。
各種時間複雜度對比
那麼有沒有平穩推進的計算事件呢？也就是O在對象增加的情況下，計算次數比較平穩增加，沒有出現類似的爆炸事件。當然有啊，比如，我們去計算一個M位的加法。我們把這個問題扔給計算機，計算機先轉換成二進位之後，就開始逐位計算，完畢之後再以十進位的方式反饋給我們。模擬計算機處理過程，我們發現，M增加時，計算次數也僅增加M次，柔順遞增，於是加法的複雜度就是O(n)。乘法呢？要稍微多一點，根據加法與乘法的遞進關係，我們可以得到乘法的複雜度為O(n2).至於除法，以及開方，立方等等運算，我們也可以很容易就歸納出複雜度大致的範圍。事實上這一類計算的複雜度為O(關於n的多項式)，有的計算問題里包含了許多種基本運算，那麼複雜度就高點，有的計算簡單純粹，那麼複雜度就低些。人們歸納得出來，有一大類問題的複雜度總是n的一個多項式表達式。換句話說，這一類問題總可以在多項式時間內被求解出來。而我們目前的計算機能夠處理的都是這樣的一類計算。
加減乘除的計算都在多項式時間內
到這裡，我們來到NP問題的第一步。上面說的總有一大類問題計算的時間複雜度是n的一個多項式，我們就把此類事件叫作P(Polynomial)問題。
千禧年七大數學難題之首——NP問題
然而，這個世界上存在著很多不一定就可以在多項式內被解決的問題。事實上，我們根本沒辦法去確定計算這些問題到底需要多少時間。假如，需要對一個有個長達1億位的大數進行因子分解，用現在的任何計算機都是徒勞無用的，可能算是宇宙毀滅也不會有結果。也有可能你的計算機很聰明，它並不是按部就班去計算每一個可能會是因子的素數，它隨機的從一堆可能的結果里找出一個數，找出一個我就驗證一個，如果不是，我就再找下一個。最終在我們可以列舉的多項式時間裡成功分解了這個超級大數。這樣一台並不按部就班的計算機就不是我們平時使用的那種你輸入什麼指令它就只能幹什麼的傻瓜機器了。於是，我們給這樣的計算機起個新奇的名字，叫非確定性計算機。就是你不知道它會用什麼方式來計算，但是它總會在有限的多項式時間內給你想要的結果。凡是符合這種情況的問題，我們就把這類問題叫作NP(Non-Deterministic Polynomial)問題。
非確定性計算機
好了，現在我們已經介紹理論這個千年難題中的兩個概念了。我們要驗證的問題就是NP問題有沒有可能和P問題是同一類。也就是說，是否存在一種非常牛逼的演算法，可以把NP的問題轉化到使用確定計算機在多項式時間內得到結果。
我們的直覺上感覺，NP類問題的複雜度應該是介於多項式時間和指數型時間之間。人們迫不及待地研究了三十多年，沒有一個人提過出一個否定或者肯定的證明。提出的都是這個猜想的猜想。
數學家們早已證明，對一個大數的分解就是NP問題。一個大數的素性檢驗工作，一不小心就會超過我們當今最厲害的超級計算機的運算能力。然而，如果給了你幾個數字，讓你去驗證是否是這個超級大數的因子卻是如此簡單。
為我們的信息安全保駕護航的RSA演算法
前面說到，RSA加密系統為什麼在當今世界如此可靠，就是基於大數分解的困難性。我們現在假設一種可怕的情形，未來的人類證明了NP=P，這就說明存在一種方法使RSA的加密演算法可以在多項式時間內被一台確定性計算機攻破。如果事實如此，那麼我們肯定會去想方設法找尋這種曠世演算法，可能這個曠世演算法人類要尋找很多很多年。但是由於我們在理論上證明了的確存在這樣的演算法，那麼找出來就是遲早的事情。若以後的人們真的證明了這個問題，那麼從宣布證明的那一刻開始，RSA演算法立馬就會走下神壇，整個互聯網交易的安全性就成為無稽之談,人們會徹頭徹尾地再設計一套全新的演算法來取代RSA,因為理論上真有這樣一種捷徑可以破解它。假如未來的人類證明了NP≠P，RSA演算法則仍然可以為人類牢固地服務很多年，直到新的更加安全的加密演算法的出現。
NP問題的提出者——斯蒂芬·庫克
1971年5月4日，斯蒂芬·庫克證明了一個非常有前景的結論：
存在一個特殊的NP問題，如果這個NP問題可以在多項式時間內求解，那麼其他任何的NP問題都可以在多項式問題內求到解。
這個問題也叫NP完全問題(也叫NPC問題)，這個問題對於人類巨大的誘惑性在哪兒呢？就是人們去尋找一種演算法來證明某個非常困難的問題，可能很久很久都沒有答案。也正是因為這個演算法找不到，所以很多重大問題一直都被擱置，沒辦法得到滿意的解答。一旦某天，某個神人找到了這個演算法，並且行之有效，一個直接的後果就是之前許許多多百思不得其解的難題都被迎刃而解，不費吹灰之力！
NP問題以一個貌似不是數學專業的核心機密卻佔據了七大難題的榜首位置，不僅僅是因為這個問題空前的難度，更重要的原因是這個問題的真或者假，又或者是不可證明都會給人類帶來巨大的改變，現在有更多具體的問題都已經證實了NP問題。遺憾的是，我們現在處在的階段是，僅僅是知道如何區分P，NP，NPC問題，對於NP問題和P問題的邊界判斷成為這裡最困難的部分。
也許我們未來的世界不存在蝴蝶效應
我們設想一下，以後的幾百年里找到了那個絕世演算法。那麼我們的計算機就不會去走那麼固定死板的道路，它就會選擇性地去做一些有目的性的計算。它們能夠在有限的時間裡給出我們之前根本沒法準確計算的結果，比如股票市場的預測，長期天氣預報，開賽之前精準預言球賽比分，甚至我們會消滅「蝴蝶效應」，讓這個世界上不存在混沌的狀態。。。
這個夢想實在太過科幻，換個角度來思考，假如那天真的到來了，也許，我們的科技也走到了盡頭了吧。
