時間復(fù)雜度大致可以被分為兩種級別芙扎，一種是O(1),O(logn),O(n^a) 等揭斧，我們把它叫做多項式級的復(fù)雜度斩披；另一種是O(a^n)和O(n!)復(fù)雜度产禾，它們是非多項式級的潦闲，其復(fù)雜度計算機往往不能承受倡缠。當我們在解決一個問題時哨免，選擇的算法通常都需要是多項式級的復(fù)雜度。
P問題：一個問題可以找到一個能在多項式的時間里解決它的算法昙沦。
eg. 最短路徑問題铁瞒，最小生成樹問題...
NP問題：可以在多項式的時間里驗證一個解的問題。
eg. 哈密頓路徑桅滋，哈密頓回路...
哈密頓回路就是NP問題慧耍，這個問題現(xiàn)在還沒有找到多項式級的算法，但是驗證一條路是否經(jīng)過了每一個頂點非常容易丐谋。
之所以要定義NP問題芍碧，是因為通常只有NP問題才可能找到多項式的算法，我們不會指望一個連多項式時間驗證一個解都不行的問題存在一個解決它的多項式級的算法号俐。
P=NP?
所有的P類問題都是NP問題泌豆，也就是說，能多項式地解決一個問題吏饿，必然能多項式的驗證一個問題的解——既然正解都出來了踪危，那么驗證任意給定的解也只需比較一下就行了蔬浙。
但是人們想知道是否所有的NP問題都是P類問題。通常所謂的NP問題贞远，其實就是探討P=NP?
NPC
約化：如果能找到一個變化法則畴博，對任意一個程序A的輸入，都能按照這個法則變換成程序B的輸入蓝仲，使兩程序的輸出結(jié)果相同俱病，那么我們說問題A可以約化為問題B。問題A可以約化為問題B有一個重要的直觀意義：B的時間復(fù)雜度高于或等于A的時間復(fù)雜度袱结。約化具有一項重要的性質(zhì)：約化具有傳遞性亮隙。
存在這樣一個NP問題，所有的NP問題都可以約化為它垢夹。換句話說溢吻，只要解決了這個問題，那么所有的NP問題就都解決了果元。這種問題就是NPC問題促王，它不只一個，而是一類問題噪漾。NPC問題是最復(fù)雜的問題硼砰。
NPC問題的定義：首先它是一個NP問題且蓬；其次所有的NP問題都可以約化到它欣硼。
既然所有的NP問題都可以約化成NPC問題，那么只要任意一個NPC問題找到了一個多項式的算法恶阴，那么所有的NP問題就都能用這個算法解決了诈胜，NP也就等于P了。但是冯事，目前NPC問題沒有多項式的有效算法焦匈，只能用指數(shù)級甚至階乘級復(fù)雜度的搜索。
eg. 3SAT, 頂點覆蓋昵仅，團缓熟，哈密頓回路...
NP-hard
NP-hard問題：所有的NP問題可以在多項式的時間規(guī)約到它。它滿足NPC問題定義的第二條但是不一定滿足第一條摔笤。NP-hard問題不一定是NP問題够滑，NP-hard問題也同樣難找到多項式級的算法。
A problem is assigned to the NP (nondeterministic polynomial time) class if it is solvable in polynomial time by a nondeterministic Turing machine.
圖靈機
圖靈機就是指一個抽象的計算機吕世，它有一條無限長的紙帶彰触，紙帶分成了一個一個的小方格。有一個機器頭在紙帶上移來移去命辖。機器頭有一組內(nèi)部狀態(tài)况毅，還有一些固定的程序分蓖。在每個時刻，機器頭都要從當前紙帶上讀入一個方格信息尔许，然后結(jié)合自己的內(nèi)部狀態(tài)查找程序表么鹤，根據(jù)程序輸出信息到紙帶方格上，并轉(zhuǎn)換自己的內(nèi)部狀態(tài)母债，然后進行移動午磁。
確定性圖靈機
每一步都唯一確定的圖靈機。設(shè)M為一個圖靈機毡们，則只要給M一個輸入迅皇，M便會以一種唯一確定的方式進行運行。即對M的同一輸入衙熔，只有一種計算過程與之相應(yīng)登颓。
非確定性圖靈機
在計算的每一時刻，根據(jù)當前狀態(tài)和讀寫頭所讀的符號红氯，機器存在多種狀態(tài)轉(zhuǎn)移方案框咙，機器將任意地選擇其中一種方案繼續(xù)運作，直到最后停機為止痢甘。
