2000年5月24日，美國克雷數(shù)學(xué)研究所，發(fā)布了新世紀(jì)最重要的七大數(shù)學(xué)難題。并為每個問題的解決懸賞一百萬美元，答題時間沒有限制。與1900年初的希爾伯特之23問遙相呼應(yīng)。

千禧年七大問題分別是：

P對NP問題， 霍奇猜想， 黎曼假設(shè)，楊－米爾斯理論存在性與質(zhì)量缺口，納維-斯托克斯方程存在性與光滑性，BSD猜想。

這里面只有NP問題是計算機界的重大問題，而且排名榜首，足見其在當(dāng)今數(shù)學(xué)界重要地位！

要了解NP問題，我們首先要去理解一個概念：時間復(fù)雜度。

假如我要在假期從合肥開始自駕游，計劃游覽完周邊，上海，南京，武漢，三個城市，然后再回到合肥來，為了節(jié)約時間，我肯定是傾向于總里程最少的線路。那么我肯定要事先做好規(guī)劃，于是我把所有可能的方案全部都列出來：

這里總共有6種方案。

然后分別計算這些方案的總里程（不考慮實際道路情況）：

我們發(fā)現(xiàn)第 4種方案里程最短，于是我們選擇這個方案。

如果我的假期足夠長，不僅僅游覽周圍3個城市，打算游遍華中10個城市呢？這種情況下，我該怎樣規(guī)劃最優(yōu)的游覽路線。用最笨的辦法，我們還是需要把所有可能的線路方案都列舉出來，于是以此類推，就有10！種方案，大約3628800種方案。到這里，我們很快就發(fā)現(xiàn)，只要城市數(shù)目稍微大一點，采用窮舉的方法就變得幾乎不可行。因為，只要我們增加到第N個城市，可能的方案數(shù)目就會是原來方案數(shù)的N倍。所有我們能夠使用枚舉的N值實在是很小，稍大一點，計算量就會遠(yuǎn)遠(yuǎn)超過我們可以承受的水平。

大家還記得那個在象棋盤上扔麥子的故事么？第一格放1粒麥子，第2格放2粒，。。。后面的麥子數(shù)目都是前一格的2倍，直到放滿64格為止。事實上，這個游戲如果真的做到最后，那么從地球上的第一顆麥粒，一直到現(xiàn)在所種出的麥子都不夠填上去。因為由于前后倍數(shù)的關(guān)系，數(shù)量很快就會急劇增大，人們給這樣極具增加的過程起了一個形象的名字，叫指數(shù)爆炸。而我們前面說的那個自駕游的增加速度遠(yuǎn)比這個指數(shù)爆炸還要恐怖地多。所以為了衡量計算過程的復(fù)雜特性，我們引入了時間復(fù)雜度這個概念。這里不是指的是計算需要的世界，而是說，隨著計算對象的增加，需要增加的計算量。

我們用這個O這個符號來記時間復(fù)雜度。棋盤麥粒問題的時間復(fù)雜度就是O(2ⁿ),前面的自駕游事件的復(fù)雜度就是O(n!)。這兩種事件的考慮對象一旦超過了某個限度，計算的次數(shù)都是任何機器都難以承受的。

那么有沒有平穩(wěn)推進的計算事件呢？也就是O在對象增加的情況下，計算次數(shù)比較平穩(wěn)增加，沒有出現(xiàn)類似的爆炸事件。當(dāng)然有啊，比如，我們?nèi)ビ嬎阋粋€M位的加法。我們把這個問題扔給計算機，計算機先轉(zhuǎn)換成二進制之后，就開始逐位計算，完畢之后再以十進制的方式反饋給我們。模擬計算機處理過程，我們發(fā)現(xiàn)，M增加時，計算次數(shù)也僅增加M次，柔順遞增，于是加法的復(fù)雜度就是O(n)。乘法呢？要稍微多一點，根據(jù)加法與乘法的遞進關(guān)系，我們可以得到乘法的復(fù)雜度為O(n²).至于除法，以及開方，立方等等運算，我們也可以很容易就歸納出復(fù)雜度大致的范圍。事實上這一類計算的復(fù)雜度為O(關(guān)于n的多項式)，有的計算問題里包含了許多種基本運算，那么復(fù)雜度就高點，有的計算簡單純粹，那么復(fù)雜度就低些。人們歸納得出來，有一大類問題的復(fù)雜度總是n的一個多項式表達式。換句話說，這一類問題總可以在多項式時間內(nèi)被求解出來。而我們目前的計算機能夠處理的都是這樣的一類計算。

到這里，我們來到NP問題的第一步。上面說的總有一大類問題計算的時間復(fù)雜度是n的一個多項式，我們就把此類事件叫作P(Polynomial)問題。

然而，這個世界上存在著很多不一定就可以在多項式內(nèi)被解決的問題。事實上，我們根本沒辦法去確定計算這些問題到底需要多少時間。假如，需要對一個有個長達1億位的大數(shù)進行因子分解，用現(xiàn)在的任何計算機都是徒勞無用的，可能算是宇宙毀滅也不會有結(jié)果。也有可能你的計算機很聰明，它并不是按部就班去計算每一個可能會是因子的素數(shù)，它隨機的從一堆可能的結(jié)果里找出一個數(shù)，找出一個我就驗證一個，如果不是，我就再找下一個。最終在我們可以列舉的多項式時間里成功分解了這個超級大數(shù)。這樣一臺并不按部就班的計算機就不是我們平時使用的那種你輸入什么指令它就只能干什么的傻瓜機器了。于是，我們給這樣的計算機起個新奇的名字，叫非確定性計算機。就是你不知道它會用什么方式來計算，但是它總會在有限的多項式時間內(nèi)給你想要的結(jié)果。凡是符合這種情況的問題，我們就把這類問題叫作NP(Non-Deterministic Polynomial)問題。

好了，現(xiàn)在我們已經(jīng)介紹理論這個千年難題中的兩個概念了。我們要驗證的問題就是NP問題有沒有可能和P問題是同一類。也就是說，是否存在一種非常牛逼的算法，可以把NP的問題轉(zhuǎn)化到使用確定計算機在多項式時間內(nèi)得到結(jié)果。

我們的直覺上感覺，NP類問題的復(fù)雜度應(yīng)該是介于多項式時間和指數(shù)型時間之間。人們迫不及待地研究了三十多年，沒有一個人提過出一個否定或者肯定的證明。提出的都是這個猜想的猜想。

數(shù)學(xué)家們早已證明，對一個大數(shù)的分解就是NP問題。一個大數(shù)的素性檢驗工作，一不小心就會超過我們當(dāng)今最厲害的超級計算機的運算能力。然而，如果給了你幾個數(shù)字，讓你去驗證是否是這個超級大數(shù)的因子卻是如此簡單。

前面說到，RSA加密系統(tǒng)為什么在當(dāng)今世界如此可靠，就是基于大數(shù)分解的困難性。我們現(xiàn)在假設(shè)一種可怕的情形，未來的人類證明了NP=P，這就說明存在一種方法使RSA的加密算法可以在多項式時間內(nèi)被一臺確定性計算機攻破。如果事實如此，那么我們肯定會去想方設(shè)法找尋這種曠世算法，可能這個曠世算法人類要尋找很多很多年。但是由于我們在理論上證明了的確存在這樣的算法，那么找出來就是遲早的事情。若以后的人們真的證明了這個問題，那么從宣布證明的那一刻開始，RSA算法立馬就會走下神壇，整個互聯(lián)網(wǎng)交易的安全性就成為無稽之談,人們會徹頭徹尾地再設(shè)計一套全新的算法來取代RSA,因為理論上真有這樣一種捷徑可以破解它。假如未來的人類證明了NP≠P，RSA算法則仍然可以為人類牢固地服務(wù)很多年，直到新的更加安全的加密算法的出現(xiàn)。

1971年5月4日，斯蒂芬·庫克證明了一個非常有前景的結(jié)論：

存在一個特殊的NP問題，如果這個NP問題可以在多項式時間內(nèi)求解，那么其他任何的NP問題都可以在多項式問題內(nèi)求到解。

這個問題也叫NP完全問題(也叫NPC問題)，這個問題對于人類巨大的誘惑性在哪兒呢？就是人們?nèi)ふ乙环N算法來證明某個非常困難的問題，可能很久很久都沒有答案。也正是因為這個算法找不到，所以很多重大問題一直都被擱置，沒辦法得到滿意的解答。一旦某天，某個神人找到了這個算法，并且行之有效，一個直接的后果就是之前許許多多百思不得其解的難題都被迎刃而解，不費吹灰之力！

NP問題以一個貌似不是數(shù)學(xué)專業(yè)的核心機密卻占據(jù)了七大難題的榜首位置，不僅僅是因為這個問題空前的難度，更重要的原因是這個問題的真或者假，又或者是不可證明都會給人類帶來巨大的改變，現(xiàn)在有更多具體的問題都已經(jīng)證實了NP問題。遺憾的是，我們現(xiàn)在處在的階段是，僅僅是知道如何區(qū)分P，NP，NPC問題，對于NP問題和P問題的邊界判斷成為這里最困難的部分。

我們設(shè)想一下，以后的幾百年里找到了那個絕世算法。那么我們的計算機就不會去走那么固定死板的道路，它就會選擇性地去做一些有目的性的計算。它們能夠在有限的時間里給出我們之前根本沒法準(zhǔn)確計算的結(jié)果，比如股票市場的預(yù)測，長期天氣預(yù)報，開賽之前精準(zhǔn)預(yù)言球賽比分，甚至我們會消滅“蝴蝶效應(yīng)”，讓這個世界上不存在混沌的狀態(tài)。。。

這個夢想實在太過科幻，換個角度來思考，假如那天真的到來了，也許，我們的科技也走到了盡頭了吧。