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

千禧年七大問題分別是：

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

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

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

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

這里總共有6種方案。

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

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

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

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

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

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

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

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

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

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

數(shù)學(xué)家們?cè)缫炎C明，對(duì)一個(gè)大數(shù)的分解就是NP問題。一個(gè)大數(shù)的素性檢驗(yàn)工作，一不小心就會(huì)超過我們當(dāng)今最厲害的超級(jí)計(jì)算機(jī)的運(yùn)算能力。然而，如果給了你幾個(gè)數(shù)字，讓你去驗(yàn)證是否是這個(gè)超級(jí)大數(shù)的因子卻是如此簡(jiǎn)單。

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

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

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

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

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

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

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