2000年5月24日，新罕布什爾州的克萊數(shù)學(xué)研究所列出了數(shù)學(xué)和計(jì)算機(jī)科學(xué)中七個(gè)未解決的問題,。解決其中任何一個(gè)問題的獎(jiǎng)勵(lì)是該研究所提供的一張100萬美元的支票,。然而，直到今天,，這些問題中只有一個(gè)被解決了,，那就是龐加萊猜想（Poincaré Conjecture）——被俄羅斯數(shù)學(xué)家格里戈里-佩雷爾曼解決。重要的是要認(rèn)識(shí)到,，這些問題的 "解 "是以數(shù)學(xué)證明的形式出現(xiàn)的,，要么否認(rèn)，要么確認(rèn)該定理,。其他六個(gè)未解決的問題之一是著名的P vs NP問題,。時(shí)間復(fù)雜度對(duì)時(shí)間復(fù)雜度的研究可以得到很好的復(fù)雜度（下面解釋）。麻省理工學(xué)院的邁克爾·西普塞（Michael Sipser）教授因其在計(jì)算復(fù)雜性理論領(lǐng)域的杰出工作而聞名,，他給出的標(biāo)準(zhǔn)定義是：讓M是一個(gè)確定性的圖靈機(jī)（ Turing machine）,，它對(duì)所有的輸入上都會(huì)停機(jī)（halt，停機(jī)問題是邏輯學(xué)的焦點(diǎn),，也是第三次數(shù)學(xué)危機(jī)的解決方案）,。M的運(yùn)行時(shí)間或時(shí)間復(fù)雜度是函數(shù)f：N→N，其中f(n)是M對(duì)任何長(zhǎng)度為n的輸入所使用的最大步驟數(shù),。習(xí)慣上我們用n來表示輸入的長(zhǎng)度,。 看完定義應(yīng)該比較懵逼吧？這到底是什么意思呢,？現(xiàn)在,，讓我們降低維度來看這個(gè)問題。一個(gè)算法的時(shí)間復(fù)雜度可以被描述為該算法在計(jì)算機(jī)上對(duì)給定輸入長(zhǎng)度的運(yùn)行時(shí)間,。確定一個(gè)給定程序的時(shí)間復(fù)雜度可能很困難,，所以計(jì)算機(jī)科學(xué)家們開發(fā)了一種稱為漸近分析（asymptotic analysis）的估計(jì)表達(dá)式，也稱為大O表示,。做好準(zhǔn)備,，另一個(gè)復(fù)雜的定義正在向你走來：讓f和g是函數(shù)f , g : N → R+。如果存在正整數(shù)c和n0,，使每個(gè)整數(shù)n≥n0,，f(n)≤cg(n)，則稱f(n)=O(g(n)),。當(dāng)f(n)=O(g(n))時(shí),，我們說g(n)是f(n)的上限，或者更準(zhǔn)確地說,，g(n)是f(n)的漸近上限,，以強(qiáng)調(diào)我們?cè)谝种瞥?shù)因素,。 讓我們暫時(shí)跳過第一部分，更仔細(xì)地看一下定義的第二部分,。我們將在這里使用一個(gè)例子：- 一個(gè)簡(jiǎn)單的C語(yǔ)言for循環(huán)
為了找到這個(gè)算法的漸進(jìn)上限,，我們必須首先分析各部分。如果本例中數(shù)組n的大小為10,，則循環(huán)將運(yùn)行10次,。在這種情況下，函數(shù)的上限將永遠(yuǎn)是n的大小,。因此,，n是漸進(jìn)的上限，計(jì)算機(jī)科學(xué)家用來描述這一事實(shí)的符號(hào)是O(n),，這被稱為線性時(shí)間（ linear time）,。- 兩個(gè)for循環(huán)的 大O是O(n^2)
這里的函數(shù)有兩個(gè)for循環(huán)，意味著如果n=10,，它將被運(yùn)行100次,，或n*n次。大O的表達(dá)是O(n^2),，或者說是平方時(shí)間（quadratic time）,。假設(shè)一個(gè)算法，我們能夠確定其時(shí)間復(fù)雜度為f(n)=4n2+2n+12,，這是否意味著大O將是O(4n2+2n+12),？重要的是再看一下定義的最后一部分，我們正在尋找漸近線,，因此我們只需要增速最快的項(xiàng)（在這種情況下是4n^2）,，并且我們?nèi)サ舫?shù)（因?yàn)槌?shù)可以根據(jù)硬件差異和限制而改變）,，最終得到一個(gè)O(n2)的大O,。那么這與上面簡(jiǎn)單的兩個(gè)for循環(huán)具有相同的大O？是的,！大O幫助計(jì)算機(jī)科學(xué)家可視化算法運(yùn)行時(shí)間的上限,，所以就所有目的而言，這兩種不同的算法具有相同的大O,。P類和NP類現(xiàn)在我們對(duì)時(shí)間復(fù)雜度有了一定的了解,，我們終于可以看看研究判定問題（ decision problems）的P和NP了。判定問題是一個(gè)有答案 "真 "或 "假 "的問題,。P：P代表多項(xiàng)式,，是兩者中比較簡(jiǎn)單的。P類可以被描述為可由算法在多項(xiàng)式時(shí)間內(nèi)解決的問題的集合,。- O(n), O(n^2), O(n^3) 都是多項(xiàng)式時(shí)間的例子,。
- 屬于P類的問題的例子包括乘法,，或者尋找一個(gè)數(shù)組中最大的整數(shù)。
NP：NP代表非確定性多項(xiàng)式,，這是兩類中比較復(fù)雜的,，它有兩種不同的可能定義。更簡(jiǎn)單的定義是,。在計(jì)算復(fù)雜性理論中,，NP（非確定性多項(xiàng)式時(shí)間）是一個(gè)用于對(duì)決策問題進(jìn)行分類的復(fù)雜性類。NP是一組決策問題,，對(duì)于這些問題,，答案是“是”，它的證明可以在多項(xiàng)式時(shí)間內(nèi)被確定性圖靈機(jī)證明,。 NP（Nondeterministic Polynomially,，非確定性多項(xiàng)式）類問題是指一個(gè)復(fù)雜問題不能確定是否在多項(xiàng)式時(shí)間內(nèi)找到答案，但是可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證答案是否正確,。最好是看一個(gè)經(jīng)典游戲來幫助直觀地了解NP問題,。數(shù)獨(dú)是我用來描述NP中問題類別的最常用的例子。- 一個(gè)正在被算法解決的數(shù)獨(dú)謎題
數(shù)獨(dú)是很容易解決的,，所以上面的算法并沒有花費(fèi)多少時(shí)間來解決它,。然而，如果這個(gè)數(shù)獨(dú)謎題從9x9增長(zhǎng)到100x100呢,？如果我們把數(shù)獨(dú)問題從9x9的輸入,，概括為采取NxN，那么這個(gè)問題很快就會(huì)變成一個(gè)NP問題,。數(shù)獨(dú)問題是很容易驗(yàn)證的,。這意味著，給定一個(gè)數(shù)獨(dú)問題的解,，存在一個(gè)多項(xiàng)式時(shí)間的算法,，可以正確驗(yàn)證該解是否正確。再次使用這個(gè)9x9的例子,，你自己可以很容易地驗(yàn)證這是否是一個(gè)正確的解,，并且設(shè)計(jì)一個(gè)算法來完成你自己的大腦在這種情況下所能完成的工作也是很簡(jiǎn)單的。然而,，要解決任何大小的數(shù)獨(dú)謎題的算法似乎就不那么簡(jiǎn)單了,，這也是事實(shí)。與NP相關(guān)的問題是NP的完備性問題,。這些問題因其難度而聞名,，因?yàn)樗鼈儧]有已知的多項(xiàng)式算法解（O(n), O(n^2)...）。這些問題可以被認(rèn)為是計(jì)算機(jī)科學(xué)中最棘手的問題。- 在O(n)中運(yùn)行100個(gè)元素要1秒的算法,，在O(n3)中運(yùn)行要3個(gè)小時(shí),。這似乎是一個(gè)很大的跳躍，一個(gè)以O(shè)(2^N)運(yùn)行的問題,，100個(gè)元素需要300quintillion（百萬的3次方）年,。因此，尋找一個(gè)多項(xiàng)式解比一個(gè)指數(shù)解更有價(jià)值,。
確定一個(gè)問題是否是NP-完備性的過程如下,。- 確定問題是否在NP中（可在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證或可由非確定性圖靈機(jī)解決）。
NP-Hard：當(dāng)事情從復(fù)雜變成更復(fù)雜,。 非正式地講，NP-Hard問題與任何NP問題一樣難或更難,。更確切地說,，任何NP-完備性問題都可以在多項(xiàng)式時(shí)間內(nèi)簡(jiǎn)化為NP-Hard問題。 解決一個(gè)NP-Hard問題的算法可以解決所有的NP-Hard問題,，因?yàn)槊總€(gè)NP-Hard問題都可以被轉(zhuǎn)化成其他問題,。這意味著解決一個(gè)NP-完備問題的方案也能解決所有其他NP-完備問題。同樣值得注意的是,，一個(gè)NP-Hard問題不一定在NP中（記?。绻仁荖P-Hard又在NP中,，我們會(huì)把它歸類為NP完備,，而且不一定是判定問題。哈密頓路徑問題（Hamiltonian Path problem）問的是對(duì)于一個(gè)給定的圖,，是否有一條路徑只訪問每個(gè)頂點(diǎn)一次,。哈密爾頓路徑問題是一個(gè)NP完備性問題的例子。要驗(yàn)證這個(gè)問題是否在NP中很簡(jiǎn)單,。- 如果沒有通往某個(gè)頂點(diǎn)的路徑，則返回false,。否則返回true,。
子集和（Subset Sum problem）問題是,，給定一個(gè)包含整數(shù)的集合S和一個(gè)目標(biāo)和（target-sum）N,，確定S中是否有一個(gè)子集的總和為N。- S={1,，3,，5，6},，N=4,。答案是 "真",，因?yàn)樽蛹瘂1，3}的總和為4,。
這個(gè)問題也是NP完備的,。要驗(yàn)證這個(gè)問題是否屬于NP，比上一個(gè)問題還要簡(jiǎn)單：- 如果它們等于N,，則返回true。否則返回false,。
也許你很難相信,，但是子集和問題和哈密頓路徑問題在函數(shù)上是等價(jià)的，因?yàn)樗鼈兌际荖P-完備的,。這意味著子集之和的解決方案可以轉(zhuǎn)化為解決哈密爾頓路徑問題,。有大量的NP-完備問題，這只是其中兩個(gè)例子,。最后：P=NP,？大多數(shù)數(shù)學(xué)家和計(jì)算機(jī)科學(xué)家會(huì)說,，No,。但我們還沒有一個(gè)明確的證明。重要的是要考慮到,，P=NP只告訴我們存在多項(xiàng)式時(shí)間的解,，而不是這些算法是什么。然而,，如果這些算法確實(shí)存在,，而且問題被解決了，那么它不僅對(duì)計(jì)算機(jī)科學(xué)領(lǐng)域,，而且對(duì)其他主要領(lǐng)域都會(huì)產(chǎn)生一些深遠(yuǎn)的影響：- 公鑰加密,，或者說我們幾乎所有的個(gè)人和可識(shí)別數(shù)據(jù)是如何被存儲(chǔ)和保護(hù)的。
- 加密哈希,，或者說很多信息是如何被加密的,，以及像比特幣這樣的系統(tǒng)是如何被保護(hù)的。
- 計(jì)算基因組學(xué),，這個(gè)領(lǐng)域的一系列問題,。
其影響可能是巨大的，因?yàn)榈阶詈?，我們?shí)際發(fā)現(xiàn)最可用的算法希望是O(n)或O(nlogn)和O(logn)--即使P=NP,，如果算法是O(n^100)，它也沒什么實(shí)際意義。這是一個(gè)我們?nèi)栽谂鉀Q的問題,，也是一個(gè)也許永遠(yuǎn)不會(huì)被解決的問題,。總結(jié)- P類問題：所有可以在多項(xiàng)式時(shí)間內(nèi)求解的判定問題構(gòu)成P類問題。
- NP類問題：所有的非確定性多項(xiàng)式時(shí)間可解的判定問題構(gòu)成NP類問題,。
- NP-hard,，指所有NP問題都能在多項(xiàng)式時(shí)間復(fù)雜度內(nèi)歸遇到的問題。
- NP完備問題（簡(jiǎn)單的寫法是 NP=P,？）：NP中的某些問題的復(fù)雜性與整個(gè)類的復(fù)雜性相關(guān)聯(lián),。這些問題中任何一個(gè)如果存在多項(xiàng)式時(shí)間的算法，那么所有NP問題都是多項(xiàng)式時(shí)間可解的,。這些問題被稱為NP-完備問題（NPC問題）,。
|
