0.參考

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

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

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

1.基本概念

a.時(shí)間復(fù)雜度

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

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

b.多項(xiàng)式級(jí)復(fù)雜度與非多項(xiàng)式級(jí)復(fù)雜度

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

c.易解問(wèn)題和難解問(wèn)題

能在多項(xiàng)式時(shí)間內(nèi)解決的問(wèn)題稱(chēng)為易解問(wèn)題，只能在指數(shù)級(jí)時(shí)間內(nèi)解決的問(wèn)題稱(chēng)為難解問(wèn)題

d.確定性計(jì)算模型（如確定性圖靈機(jī)）與非確定性計(jì)算模型（如非確定性圖靈機(jī)）

確定性計(jì)算模型：對(duì)于輸入，輸出的是確定的單值

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

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

2.P問(wèn)題和NP問(wèn)題

a.P（polynomial，多項(xiàng)式）問(wèn)題

定義1：如果一個(gè)問(wèn)題可以找到一個(gè)能在多項(xiàng)式的時(shí)間里解決它的算法，那么這個(gè)問(wèn)題就屬于P問(wèn)題。

定義2：P類(lèi)問(wèn)題是確定性計(jì)算模型下的易解問(wèn)題

b.NP（Non-Deterministic Polynomial，非確定多項(xiàng)式）問(wèn)題

定義1：NP問(wèn)題是指可以在多項(xiàng)式的時(shí)間里驗(yàn)證一個(gè)解的問(wèn)題。NP問(wèn)題的另一個(gè)定義是，可以在多項(xiàng)式的時(shí)間里猜出一個(gè)解的問(wèn)題。

定義2：NP類(lèi)問(wèn)題是非確定性計(jì)算模型下的易驗(yàn)證問(wèn)題

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

c.P與NP

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

3.NPC問(wèn)題

a.定義及描述

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

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

b.證明一個(gè)問(wèn)題是NP完全問(wèn)題

證明一個(gè)NP問(wèn)題是一個(gè)NPC問(wèn)題依賴(lài)三個(gè)關(guān)鍵概念

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

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

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

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

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

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

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

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

3）第一個(gè)NPC問(wèn)題

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

c.NPC問(wèn)題的求解方式

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

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

3）概率算法（章七）

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

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

d.一些典型的NP完全問(wèn)題

4.NP-hand問(wèn)題

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