“P=NP?” 通常被認(rèn)為是計(jì)算機(jī)科學(xué)最重要的問題,。有一個叫 Clay Math 的研究所，甚至懸賞 100 萬美元給解決它的人,?？墒俏医裉煲嬖V你的是，這個問題其實(shí)遠(yuǎn)遠(yuǎn)不是那么的重要,。

　　我并不是第一個這樣認(rèn)為的人,。在很早的時候，就有一位數(shù)學(xué)家毫不客氣的指出,，P=NP? 是個愚蠢的問題,，并且為了嘲笑這個問題，專門在 4 月 1 號寫了一篇“論文”,，稱自己證明了 P=NP,。我身邊有一些非常聰明的人，他們基本也都不把這問題當(dāng)回事,。如果我對他們講這些東西,，恐怕已經(jīng)是老生常談，所以我只是在這里科普一下,。

　　首先,，你要先搞清楚什么是“P=NP?” 為此，你必須先了解一下什么是“算法復(fù)雜度”,。為此,，你又必須先了解什么是“算法”。

　　你可以簡單的把“算法”想象成一臺機(jī)器,，就跟絞肉機(jī)似的,。你給它一些“輸入”,，它就給你一些“輸出”。比如,，絞肉機(jī)的輸入是肉末,，輸出是肉渣。牛的輸入是草,，輸出是奶（或者牛糞）,。“加法器”的輸入是兩個整數(shù),，輸出是這兩個整數(shù)的和,。“算法理論”所討論的問題,，就是如何設(shè)計(jì)這些機(jī)器,，讓它們更加有效的工作。就像是說如何培育出優(yōu)質(zhì)的奶牛,，吃進(jìn)相同數(shù)量的草，更快的產(chǎn)出更多的奶,。

　　世界上的計(jì)算問題,，都需要“算法”經(jīng)過一定時間的工作（也叫“計(jì)算”），才能得到結(jié)果,。計(jì)算所需要的時間,，往往跟“輸入”的大小有關(guān)系。如果你的奶牛吃了很多草,，它就需要很長時間才能把它們變成奶,。這種草和奶的轉(zhuǎn)換速度，通常被叫做“算法復(fù)雜度”,。

　　算法復(fù)雜度通常被表示為一個函數(shù) f (n),，其中 n 是輸入的大小。比如,，如果你的算法復(fù)雜度為 n^2,，那么當(dāng)輸入 10 個數(shù)據(jù)的時候，它需要 100 個單元的時間才能完成計(jì)算,。當(dāng)輸入 100 個數(shù)據(jù)的時候,，它需要 10000 個單元的時間才能完成計(jì)算。當(dāng)輸入 1000 個數(shù)據(jù)的時候,，它需要 1000000 個單元的時間,。簡單吧。

　　所謂的“P時間”,，就是“Polynomial time”,，多項(xiàng)式時間,。簡而言之，就是說這個復(fù)雜度函數(shù) f (n) 是一個多項(xiàng)式,。多項(xiàng)式你該知道是什么吧,？不知道的話，就翻一下中學(xué)數(shù)學(xué)課本,。

　　“P=NP?”中的“P”,，就是指所有這些復(fù)雜度為多項(xiàng)式的算法的“集合”，也就是指“所有”的復(fù)雜度為多項(xiàng)式的算法,。

　　現(xiàn)在我來解釋一下什么是 NP,。通常的計(jì)算機(jī)，都是確定性（deterministic）的,。它們在同樣的條件下,，只有同一種行為方式。如果用程序來表示,，那么它們遇到一個條件判斷的時候,，只能一次探索一條路徑。比如：

if (x == 0) {
  one ();
} else {
  two ();
}

　　在這里,，根據(jù) x 的值是否為零,，one () 和 two () 這兩個操作，其中只有一個可能會發(fā)生,。

　　然而,，有人幻想出來一種機(jī)器，叫做“非確定性計(jì)算機(jī)”（Nondeterministic computer）,，它可以同時運(yùn)行這程序的兩個分支,，one () 和 two ()。這有什么用處呢,？它的用處就在于,，當(dāng)你不知道 x 的大小的時候，根據(jù) one () 和 two () 是否“成功”,，你可以推斷出 x 是否為零,。

　　這種非確定性的計(jì)算機(jī)，通常被“計(jì)算理論”的研究者叫做“非確定性圖靈機(jī)”,。與之相對的就是通常所說的“計(jì)算機(jī)”,，也叫“確定性圖靈機(jī)”。其實(shí),，“圖靈機(jī)”的名字在這里完全無關(guān)緊要,。你只需要知道，非確定性的計(jì)算機(jī),，可以同時探索多種可能性,。

　　這不是普通的“并行計(jì)算”,，因?yàn)槊慨?dāng)遇到一個分支點(diǎn)，非確定性計(jì)算機(jī)就會產(chǎn)生新的計(jì)算單元,，用以同時探索這些路徑,。這機(jī)器就像有“分身術(shù)”一樣。當(dāng)這種分支點(diǎn)存在于循環(huán)里的時候,，它就會反復(fù)的產(chǎn)生新的計(jì)算單元,。所以一般的計(jì)算機(jī)，都不可能達(dá)到非確定計(jì)算機(jī)的這種“超能力”,。它們只能先探索一條路徑,，失敗之后，再回過頭來探索另外一條,。

　　到這里,，基本的概念都被定義了。于是,，我們可以圓滿的給出 P 和 NP 的定義,。P 和 NP 是這樣兩個“問題的集合”：

　　P = “確定性計(jì)算機(jī)”能夠在“多項(xiàng)式時間”解決的所有問題

　　NP = “非確定性計(jì)算機(jī)”能夠在“多項(xiàng)式時間”解決的所有問題

　　主意它們的區(qū)別，僅在于“確定性”或者是“非確定性”,。為了簡要的描述以下的內(nèi)容,，我再定義一個概念：

　　“f(n) 時間算法” = “能夠在 f (n) 時間之內(nèi)，解決某個問題的算法（機(jī)器）”

　　當(dāng) f (n) 是個多項(xiàng)式的時候,，這就是“多項(xiàng)式時間算法”（P時間算法）。當(dāng) f (n) 是個指數(shù)函數(shù)的時候,，這就是“指數(shù)時間算法”,。

　　定義完畢。現(xiàn)在回到對“P=NP?”問題的討論,。

　　“P=NP?”問題的主旨,，就在于探索 P 和 NP 這兩個集合是否相等。為了證明兩個集合（A 和 B）相等,，一般都要證明兩個方向：

　　1. A 包含 B

　　2. B 包含 A

　　你也許已經(jīng)看出來了,，NP 肯定包含了 P。因?yàn)槿魏我粋€非確定性機(jī)器,，都能被當(dāng)成一個確定性的機(jī)器來用,。你只需要不使用它的“超能力”，在每個分支點(diǎn)只探索一條路徑就行,。所以“P=NP?”問題的關(guān)鍵,，就在于 P 是否也包含了 NP。也就是說,，如果只使用“確定性計(jì)算機(jī)”,，能否在“多項(xiàng)式時間”之內(nèi),，解決任何“非確定性計(jì)算機(jī)”能在多項(xiàng)式時間內(nèi)解決的問題。

　　這里的“所有”,，其實(shí)是這個問題的關(guān)鍵所在,，也是它致命的弱點(diǎn)。如果只是針對某一個特定的問題,，試圖尋找多項(xiàng)式時間算法,，或者證明其不存在，雖然不大精確,，但確實(shí)是有一定的意義,。但是如果想要證明“所有”的 NP 問題，都有 P 時間算法,，就沒有多大用處了,。下面我簡要的說一下原因。

　　首先,，我們來細(xì)看一下什么是多項(xiàng)式時間（Polynomial time）,。我們都知道，n^2 是多項(xiàng)式,，n^1000000 也是多項(xiàng)式,。多項(xiàng)式與多項(xiàng)式之間，卻有天壤之別,。把解決問題所需要的時間,，用“多項(xiàng)式”這么籠統(tǒng)的概念來描述，其實(shí)是非常不準(zhǔn)確的做法,。在實(shí)際的大規(guī)模應(yīng)用中,，n^2 的算法都嫌慢。能找到“多項(xiàng)式時間”的算法,，根本不能說明任何問題,。

　　對此，理論家們喜歡說,，就算再大的多項(xiàng)式(比如 n^1000000),，也不能和再小的指數(shù)函數(shù)（比如 1.0001^n）相比。因?yàn)榭偸恰按嬖凇币粋€ M,，當(dāng) n > M 的時候,，1.0001^n 會超過 n^1000000?？墒菃栴}的關(guān)鍵,，往往就在于 M 的大小。如果你的輸入必須達(dá)到天文數(shù)字才能讓指數(shù)函數(shù)超過多項(xiàng)式的話，那么還不如就用指數(shù)復(fù)雜度的算法,。所以,，“P=NP?”這個問題的錯誤就在于，它并沒有針對我們的實(shí)際需要,，而是首先假設(shè)了我們有“無窮大”的輸入,，可以讓多項(xiàng)式時間的算法“最終”得到優(yōu)勢。

　　為了顯示這個問題,，我們可以畫一個坐標(biāo)曲線,，來比較一下 n^1000000 與 2^n，并且解出它們相等時的 n,。我沒有用 1.0001^n,，以免有人說我不公平。我喜歡偷懶,，經(jīng)常用 Mathematica 來解決這些算式,。下面就是我得出的結(jié)果和曲線圖：　　

　　所以你看到了，在 M< 24549200 的時候,，2^n 都是有優(yōu)勢的,。所以當(dāng)我的輸入沒有達(dá)到 2 千萬這個量級的時候，2^n 的算法會比 n^1000000 快,。

n^1000000 也許不說明問題,，但是“多項(xiàng)式”的范圍實(shí)在太大了。n^(10^100) 是多項(xiàng)式,，n^(10^(10^100)),，…… 都是多項(xiàng)式。實(shí)際上,，只要 c 是個常數(shù),，任何常數(shù)，n^c 就是個多項(xiàng)式,。你知道 n 需要多大，2^n 才能超過 n^(10^100) 嗎,？如果你知道 10^100 已經(jīng)大于宇宙中基本粒子的數(shù)目,，你也許就會意識到，當(dāng)時間復(fù)雜度達(dá)到 n^(10^100) 的時候,，所有的計(jì)算都失去了意義,。

　　于是你就發(fā)現(xiàn)，“多項(xiàng)式時間”其實(shí)是是多么粗淺的標(biāo)準(zhǔn),。試圖找到“多項(xiàng)式時間”的算法來解決所有的 NP 問題,，其實(shí)是一個徒勞的目標(biāo)。所以，“P=NP?”根本就不需要答案,，因?yàn)樗且粋€錯誤的問題,。