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