0.參考

http://www./blog/archives/105（極好，通俗易懂）

《算法導(dǎo)論》NP完全性

《算法設(shè)計與分析》NP完全性理論

1.基本概念

a.時間復(fù)雜度

定義：時間復(fù)雜度并不是表示一個程序解決問題需要花費多少時間，而是當(dāng)一個問題規(guī)模擴大以后，程序需要的時間長度增長得有多快

例子：冒泡排序、插入排序等，數(shù)據(jù)擴大2倍，時間變慢4倍的，屬于O(n^2)的復(fù)雜度

b.多項式級復(fù)雜度與非多項式級復(fù)雜度

一種是O(1),O(log(n)),O(n^a)等，我們把它叫做多項式級的復(fù)雜度，因為它的規(guī)模n出現(xiàn)在底數(shù)的位置。另一種是O(a^n)和O(n!)型復(fù)雜度，它是非多項式級的，其復(fù)雜度計算機往往不能承受。

c.易解問題和難解問題

能在多項式時間內(nèi)解決的問題稱為易解問題，只能在指數(shù)級時間內(nèi)解決的問題稱為難解問題

d.確定性計算模型（如確定性圖靈機）與非確定性計算模型（如非確定性圖靈機）

確定性計算模型：對于輸入，輸出的是確定的單值

非確定性計算模型：對于輸入，輸出的是值集，值集中的每個元素都可以作為解

區(qū)別：確定性計算模型的每一步只有一種選擇，非確定性計算模型的每一步卻有多種選擇

2.P問題和NP問題

a.P（polynomial，多項式）問題

定義1：如果一個問題可以找到一個能在多項式的時間里解決它的算法，那么這個問題就屬于P問題。

定義2：P類問題是確定性計算模型下的易解問題

b.NP（Non-Deterministic Polynomial，非確定多項式）問題

定義1：NP問題是指可以在多項式的時間里驗證一個解的問題。NP問題的另一個定義是，可以在多項式的時間里猜出一個解的問題。

定義2：NP類問題是非確定性計算模型下的易驗證問題

例子：比方說，我RP很好，在程序中需要枚舉時，我可以一猜一個準(zhǔn)?，F(xiàn)在某人拿到了一個求最短路徑的問題，問從起點到終點是否有一條小于100個單位長度的路線。它根據(jù)數(shù)據(jù)畫好了圖，但怎么也算不出來，于是來問我：你看怎么選條路走得最少？我說，我RP很好，肯定能隨便給你指條很短的路出來。然后我就胡亂畫了幾條線，說就這條吧。那人按我指的這條把權(quán)值加起來一看，嘿，神了，路徑長度98，比100小。于是答案出來了，存在比100小的路徑。別人會問他這題怎么做出來的，他就可以說，因為我找到了一個比100小的解。在這個題中，找一個解很困難（窮舉），但驗證一個解很容易。驗證一個解只需要O(n)的時間復(fù)雜度，也就是說我可以花O(n)的時間把我猜的路徑的長度加出來。那么，只要我RP好，猜得準(zhǔn)，我一定能在多項式的時間里解決這個問題。我猜到的方案總是最優(yōu)的，不滿足題意的方案也不會來騙我去選它。這就是NP問題。

c.P與NP

之所以要定義NP問題，是因為通常只有NP問題才可能找到多項式的算法。我們不會指望一個連多項式地驗證一個解都不行的問題存在一個解決它的多項式級的算法。相信讀者很快明白，信息學(xué)中的號稱最困難的問題——“NP問題”，實際上是在探討NP問題與P類問題的關(guān)系。
很顯然，所有的P類問題都是NP問題。也就是說，能多項式地解決一個問題，必然能多項式地驗證一個問題的解——既然正解都出來了，驗證任意給定的解也只需要比較一下就可以了。關(guān)鍵是，人們想知道，是否所有的NP問題都是P類問題。我們可以再用集合的觀點來說明。如果把所有P類問題歸為一個集合P中，把所有NP問題劃進(jìn)另一個集合NP中，那么，顯然有P屬于NP。現(xiàn)在，所有對NP問題的研究都集中在一個問題上，即究竟是否有P=NP？通常所謂的“NP問題”，其實就一句話：證明或推翻P=NP。

3.NPC問題

a.定義及描述

定義：滿足兩個條件，1）該問題是個NP問題，2）所有的NP問題都可以歸約成該問題

描述：從約化的定義中我們看到，一個問題約化（歸約）為另一個問題，時間復(fù)雜度增加了，問題的應(yīng)用范圍也增大了。通過對某些問題的不斷約化，我們能夠不斷尋找復(fù)雜度更高，但應(yīng)用范圍更廣的算法來代替復(fù)雜度雖然低，但只能用于很小的一類問題的算法。再回想前面講的P和NP問題，聯(lián)想起約化的傳遞性，自然地，我們會想問，如果不斷地約化上去，不斷找到能“通吃”若干小NP問題的一個稍復(fù)雜的大NP問題，那么最后是否有可能找到一個時間復(fù)雜度最高，并且能“通吃”所有的NP問題的這樣一個超級NP問題？答案居然是肯定的。也就是說，存在這樣一個NP問題，所有的NP問題都可以約化成它。換句話說，只要解決了這個問題，那么所有的NP問題都解決了。這種問題的存在難以置信，并且更加不可思議的是，這種問題不只一個，它有很多個，它是一類問題。這一類問題就是傳說中的NPC問題，也就是NP-完全問題。

b.證明一個問題是NP完全問題

證明一個NP問題是一個NPC問題依賴三個關(guān)鍵概念

1）判定問題和最優(yōu)化問題

概念：讓程序解決一個問題，輸出一個“YES”或“NO”（這被稱為判定性問題）。一個什么什么的最優(yōu)值（這被稱為最優(yōu)化問題）。NP完全性不直接適用于最優(yōu)化問題，但適合于判定問題。盡管證明一個問題是NP完全問題會使我們的目光局限于判定問題，但是我們?nèi)匀豢梢酝ㄟ^對待優(yōu)化的值強加一個界，來將一個最優(yōu)化問題轉(zhuǎn)化成判定問題的方式來證明一個最優(yōu)化問題是不是NPC問題

例子：給定一個有向圖G、頂點u，v，求u到v最短路徑（這是一個最優(yōu)化問題，shortest path）。加上界限權(quán)值和k，問題變成了這樣：給定一個有向圖G、頂點u，v，和權(quán)值和k，求u到v是否存在一條或多條路徑，滿足路徑的邊權(quán)值和小于k（這是一個判定問題，path）。通過加上界限權(quán)值和k，一個最優(yōu)化問題就轉(zhuǎn)化成了一個判定問題

證明一個最優(yōu)化問題是判定問題：在我們試圖證明一個最優(yōu)化問題是一個NPC問題時，就可以利用該問題與相關(guān)的判定問題之間的關(guān)系，一般來說，判定問題要“更容易一些”或“至少不會更難”（例如，我們可以先求出shorest path問題，然后再通過shortest path的解與k比較得出path問題的解）。也就是說，某個最優(yōu)化問題比較容易的話，相關(guān)的判定問題也比較容易，換句話說，如果我們能夠證明相關(guān)的判定問題是個NPC問題的話，那么該最優(yōu)化問題也會是一個NPC問題。

2）約化（Reducibility，有的資料上叫“歸約”）

定義：一個問題A可以約化為問題B的含義即是，可以用問題B的解法解決問題A，或者說，問題A可以“變成”問題B。（最優(yōu)化問題可以約化為判定問題，判定問題也可以約化成為另一個判定問題）

例子：現(xiàn)在有兩個問題：求解一個一元一次方程和求解一個一元二次方程。那么我們說，前者可以約化為后者，意即知道如何解一個一元二次方程那么一定能解出一元一次方程。我們可以寫出兩個程序分別對應(yīng)兩個問題，那么我們能找到一個“規(guī)則”，按照這個規(guī)則把解一元一次方程程序的輸入數(shù)據(jù)變一下，用在解一元二次方程的程序上，兩個程序總能得到一樣的結(jié)果。這個規(guī)則即是：兩個方程的對應(yīng)項系數(shù)不變，一元二次方程的二次項系數(shù)為0。按照這個規(guī)則把前一個問題轉(zhuǎn)換成后一個問題，兩個問題就等價了。同樣地，我們可以說，Hamilton回路可以約化為TSP問題(Travelling Salesman Problem，旅行商問題)：在Hamilton回路問題中，兩點相連即這兩點距離為0，兩點不直接相連則令其距離為1，于是問題轉(zhuǎn)化為在TSP問題中，是否存在一條長為0的路徑。Hamilton回路存在當(dāng)且僅當(dāng)TSP問題中存在長為0的回路。

另外： “問題A可約化為問題B”有一個重要的直觀意義：B的時間復(fù)雜度高于或者等于A的時間復(fù)雜度。也就是說，問題A不比問題B難。這很容易理解。既然問題A能用問題B來解決，倘若B的時間復(fù)雜度比A的時間復(fù)雜度還低了，那A的算法就可以改進(jìn)為B的算法，兩者的時間復(fù)雜度還是相同。正如解一元二次方程比解一元一次方程難，因為解決前者的方法可以用來解決后者。

3）第一個NPC問題

根據(jù)約化技術(shù)的定義來證明一個問題是NPC問題的前提是：我們已經(jīng)知道了一個NPC問題。我們將使用的這第一個問題是電路可滿足性問題。

c.NPC問題的求解方式

1）枚舉（回溯法）（章五）

2）動態(tài)規(guī)劃法和分支限界（章三和章六）

3）概率算法（章七）

4）近似算法求解近似值（章九）

5）啟發(fā)式方法求解（貪心（簡單直接的啟發(fā)式方法）（章四），禁忌搜索等（現(xiàn)代優(yōu)化算法））

d.一些典型的NP完全問題

4.NP-hand問題

NP-Hard問題是這樣一種問題，它滿足NPC問題定義的第二條但不一定要滿足第一條（就是說，NP-Hard問題要比NPC問題的范圍廣）。NP-Hard問題同樣難以找到多項式的算法，但它不列入我們的研究范圍，因為它不一定是NP問題。即使NPC問題發(fā)現(xiàn)了多項式級的算法，NP-Hard問題有可能仍然無法得到多項式級的算法。事實上，由于NP-Hard放寬了限定條件，它將有可能比所有的NPC問題的時間復(fù)雜度更高從而更難以解決。