《算法設(shè)計(jì)與分析基礎(chǔ)》（Python語(yǔ)言描述） 課件 第9章NP完全問(wèn)題

第9章最難問(wèn)題—NP完全問(wèn)題9.1P類和NP類9.2多項(xiàng)式時(shí)間變換和NP完全問(wèn)題CONTENTS提綱1/442/44算法呈現(xiàn)不同的時(shí)間復(fù)雜度，有的屬于多項(xiàng)式級(jí)時(shí)間復(fù)雜度算法，有的屬于指數(shù)級(jí)時(shí)間復(fù)雜度算法，指數(shù)函數(shù)是典型的非多項(xiàng)式函數(shù)。通常將存在多項(xiàng)式時(shí)間算法的問(wèn)題看作是易解問(wèn)題，不存在多項(xiàng)式時(shí)間算法的問(wèn)題看作是難解問(wèn)題。9.1.1易解問(wèn)題和難解問(wèn)題9.1P類和NP類3/44通常把多項(xiàng)式時(shí)間復(fù)雜性作為易解問(wèn)題與難解問(wèn)題的分界線。問(wèn)題規(guī)模n

多項(xiàng)式函數(shù)指數(shù)函數(shù)log2n

nnlog2n

n2

n32nn!1010.01121103.31033.2100100010243628800204.32086.4400800010483762.4E18505.650282.225001250001.0E153.0E641006.6100664.41000010000001.3E309.3E1574/44

定義9.1設(shè)A是求解問(wèn)題Ⅱ（可以是任意問(wèn)題）的算法，在用A求解問(wèn)題Ⅱ的實(shí)例Ⅰ時(shí)，首先要把I編碼成二進(jìn)制的字符串作為A的輸入，稱I的二進(jìn)制編碼的長(zhǎng)度為I的規(guī)模，記為|I|，如果存在函數(shù)f：N→N（N為自然數(shù)集合）使得對(duì)于任意規(guī)模為n的實(shí)例I，A對(duì)I的運(yùn)算在f(n)步內(nèi)停止，則稱算法A的時(shí)間復(fù)雜度為f(n)。

以多項(xiàng)式為時(shí)間復(fù)雜度的算法稱為多項(xiàng)式時(shí)間算法。有多項(xiàng)式時(shí)間的問(wèn)題稱為易解問(wèn)題，不存在多項(xiàng)式時(shí)間算法的問(wèn)題稱為難解問(wèn)題。輸入帶a1a2…ai…anBB……讀寫頭有限狀態(tài)控制器5/44采用動(dòng)態(tài)規(guī)劃算法求解0/1背包問(wèn)題的時(shí)間復(fù)雜度為O(nW)。表面上看起來(lái)這是n的多項(xiàng)式，實(shí)際上這里|I|是n和W的二進(jìn)制位數(shù)和，當(dāng)W很大時(shí)，仍然是一個(gè)非多項(xiàng)式時(shí)間的算法。TSP和0/1背包問(wèn)題等在內(nèi)的一大批問(wèn)題既沒(méi)有找到它們的多項(xiàng)式時(shí)間算法，又沒(méi)能證明它們是難解問(wèn)題。6/449.1.2判定問(wèn)題如果一個(gè)問(wèn)題很容易重述為它的解只有兩個(gè)結(jié)論即yes和no，稱為判定問(wèn)題Ⅱ。與此對(duì)照，最優(yōu)化問(wèn)題Ⅱ'是關(guān)心某個(gè)量的最大化或者最小化的問(wèn)題。例如，前面討論的TSP問(wèn)題屬于最優(yōu)化問(wèn)題Ⅱ'，對(duì)應(yīng)的TSP判定問(wèn)題Ⅱ是這樣的，假設(shè)有一個(gè)貨郎擔(dān)要拜訪n個(gè)城市，城市圖采用鄰接矩陣表示，給定一個(gè)正整數(shù)D，問(wèn)有一條每個(gè)城市恰好經(jīng)過(guò)一次最后回到出發(fā)城市并且路徑長(zhǎng)度不超過(guò)D的路徑嗎？7/44那么TSP最優(yōu)化問(wèn)題會(huì)不會(huì)比TSP判定問(wèn)題容易呢？如果TSP最優(yōu)化問(wèn)題有多項(xiàng)式時(shí)間算法A，則可以按如下方式構(gòu)造TSP判定問(wèn)題的算法B：對(duì)于任意一個(gè)實(shí)例I，應(yīng)用算法A求出最短路徑長(zhǎng)度d，如果d≤D，則算法B輸出yes，否則輸出no。顯然算法B也是多項(xiàng)式時(shí)間算法。于是，這同樣表明如果TSP判定問(wèn)題是難解問(wèn)題，則TSP最優(yōu)化問(wèn)題也是難解問(wèn)題，這樣說(shuō)明TSP最優(yōu)化問(wèn)題不會(huì)比TSP判定問(wèn)題容易。8/44一般地，如果一個(gè)問(wèn)題的可行解是多項(xiàng)式時(shí)間算法可求的，那么如果其判定問(wèn)題Ⅱ是難解問(wèn)題，則對(duì)應(yīng)的最優(yōu)化問(wèn)題Ⅱ'也是難解問(wèn)題?？梢宰C明反過(guò)來(lái)也是對(duì)的，如果最優(yōu)化問(wèn)題Ⅱ'是難解問(wèn)題，則對(duì)應(yīng)的判定問(wèn)題Ⅱ也是難解問(wèn)題。判定問(wèn)題Ⅱ和對(duì)應(yīng)的最優(yōu)化問(wèn)題Ⅱ'具有相同的難度。9/449.1.3P類定義9.2設(shè)A是求解問(wèn)題Ⅱ的一個(gè)算法，如果對(duì)于任意一個(gè)實(shí)例I在整個(gè)執(zhí)行過(guò)程中每一步都只有一種選擇，則稱A為確定性算法。因此對(duì)于同樣的輸入確定性算法的輸出是相同的。前面所有討論的算法均為確定性算法，實(shí)際上是指算法的確定性，是算法的重要特性之一。10/44定義9.3判定問(wèn)題的P類由這樣的判定問(wèn)題組成，它們的yes/no解可以用確定性算法在運(yùn)行多項(xiàng)式時(shí)間內(nèi)得到。簡(jiǎn)單地說(shuō)所有多項(xiàng)式時(shí)間可解的判定問(wèn)題類稱為P類。一個(gè)判定問(wèn)題是易解問(wèn)題當(dāng)且僅當(dāng)它屬于P類。11/44【例9-1】證明求最長(zhǎng)公共子序列問(wèn)題是易解問(wèn)題。證明：求最長(zhǎng)公共子序列原問(wèn)題是給定兩個(gè)序列a=（a0,a1,…,am-1），b=（b0,b1,…,bn-1），求它們的最長(zhǎng)公共子序列的長(zhǎng)度d。對(duì)應(yīng)的判定問(wèn)題：給定一個(gè)正整數(shù)D，問(wèn)存在a和b的長(zhǎng)度不小于D的公共子序列嗎？可以設(shè)計(jì)這樣的算法B，先利用8.5.1節(jié)求最長(zhǎng)公共子序列長(zhǎng)度的算法LCSlength()求出d，其時(shí)間復(fù)雜度為O(mn)，屬于多項(xiàng)式時(shí)間算法，如果d≤D，則輸出yes，否則輸出no。顯然算法B也是多項(xiàng)式時(shí)間算法，所以LCS屬于P類即是易解問(wèn)題。12/449.1.4NP類對(duì)于輸入x，一個(gè)不確定性算法由下列兩個(gè)階段組成。猜測(cè)階段。在這個(gè)階段產(chǎn)生一個(gè)任意字符串y，它可能對(duì)應(yīng)于輸入實(shí)例的一個(gè)解，也可以不對(duì)應(yīng)解。事實(shí)上，它甚至可能不是所求解的合適形式，它可能在不確定性算法的不同次運(yùn)行中不同。它僅僅要求在多項(xiàng)式步數(shù)內(nèi)產(chǎn)生這個(gè)串，即時(shí)間為O(ni)，這里n=|x|，i是非負(fù)整數(shù)。對(duì)于許多問(wèn)題，這一階段可以在線性時(shí)間內(nèi)完成。13/44②

驗(yàn)證階段。在這個(gè)階段一個(gè)不確定性算法驗(yàn)證兩件事。首先檢查產(chǎn)生的解串y是否有合適的形式，如果不是則算法停下并回答no。另一方面，如果y是合適形式，那么算法繼續(xù)檢查它是否是問(wèn)題實(shí)例x的解，如果它確實(shí)是實(shí)例x的解，那么它停下并且回答yes，否則它停下并回答no。也要求這個(gè)階段在多項(xiàng)式步數(shù)內(nèi)完成。14/44定義9.4設(shè)A是求解問(wèn)題Ⅱ的一個(gè)不確定性算法，A接受問(wèn)題Ⅱ的實(shí)例I當(dāng)且僅當(dāng)對(duì)于輸入I存在一個(gè)導(dǎo)致yes回答的猜測(cè)。換句話說(shuō)，A接受I當(dāng)且僅當(dāng)可能在算法的某次執(zhí)行上它的驗(yàn)證階段將回答yes。如果算法回答no，那么這并不意味著A不接受它的輸入，因?yàn)樗惴赡懿聹y(cè)了一個(gè)不正確解。15/44例如，不確定性算法A的偽碼表示如下：1 defA(I):2 s=genCertif() #猜測(cè)階段3 checkOK=verifyA(I,s) #驗(yàn)證階段4 ifcheckOK:5 output"yes"6 return #checOK為假時(shí)不作反應(yīng)16/44定義9.5判定問(wèn)題的NP類由這樣的判定問(wèn)題組成，對(duì)于它們存在著多項(xiàng)式時(shí)間內(nèi)運(yùn)行的不確定性算法。簡(jiǎn)單地說(shuō)由所有多項(xiàng)式時(shí)間可驗(yàn)證的判定問(wèn)題類稱為NP類。要注意的是不確定性算法并不是真正的算法，它僅僅是為了刻畫可驗(yàn)證性而提出的驗(yàn)證概念。為了把不確定性多項(xiàng)式時(shí)間算法轉(zhuǎn)換為確定性算法，必須搜索整個(gè)可能的解空間，注通常需要指數(shù)時(shí)間。17/44定義9.6NP類的非形式化定義是NP類由這樣的判定問(wèn)題組成，它們存在一個(gè)確定性算法，該算法在對(duì)問(wèn)題的一個(gè)實(shí)例展示一個(gè)斷言解時(shí)，它能夠在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證解的正確性，也就是說(shuō)如果斷言解導(dǎo)致答案是yes，就存在一種方法可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證這個(gè)解。18/44【例9-2】給定一個(gè)無(wú)向圖G=（V，E），用k種顏色對(duì)G著色是這樣的問(wèn)題，對(duì)于V中的每一個(gè)頂點(diǎn)有k種顏色中的一種對(duì)它著色，使圖中沒(méi)有兩個(gè)相鄰頂點(diǎn)有相同的顏色。著色問(wèn)題是判定用預(yù)定數(shù)目的顏色對(duì)一個(gè)無(wú)向圖著色是否可能。證明該問(wèn)題屬于NP問(wèn)題。19/44證明：對(duì)于的判斷問(wèn)題是給定一個(gè)無(wú)向圖G=（V，E）和一個(gè)正整數(shù)k（k≥1），G可以k著色嗎？用兩種方法證明上述判斷問(wèn)題COLORING屬于NP類問(wèn)題。方法1：設(shè)I是COLORING問(wèn)題的一個(gè)實(shí)例，s被宣稱為I的解。容易建立一個(gè)確定性算法來(lái)驗(yàn)證s是否確實(shí)是I的解（假設(shè)s為著色數(shù)目，一定同時(shí)求出一個(gè)對(duì)應(yīng)的著色方案x，檢測(cè)x是否為G的一個(gè)s顏色的著色方案只需要遍歷每一條邊即可）。從定義9.6可以得出COLORING屬于NP類。20/44方法2：建立不確定性算法.當(dāng)圖G用編碼表示后，很容易地構(gòu)建算法A：首先通過(guò)對(duì)頂點(diǎn)集合產(chǎn)生一個(gè)任意的顏色“猜測(cè)”為一個(gè)解s，接著A驗(yàn)證這個(gè)s是否為有效解，如果它是一個(gè)有效解，那么A停下并且回答yes，否則它停下并回答no。A在猜測(cè)和驗(yàn)證兩個(gè)階段總共花費(fèi)不多于多項(xiàng)式時(shí)間，所以COLORING屬于NP類。21/44定理9.1P

NP。證明：這是顯而易見(jiàn)的。如果某個(gè)問(wèn)題Ⅱ?qū)儆赑類，則它有一個(gè)確定性的求解算法A。很容易由算法A構(gòu)造出這樣的算法B，算法B對(duì)該問(wèn)題的一個(gè)實(shí)例展示一個(gè)斷言解時(shí)，它一定能夠在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證解的正確性，所以問(wèn)題Ⅱ也屬于P類。現(xiàn)在的問(wèn)題是P=NP?也就是說(shuō)NP類中有難解問(wèn)題嗎？22/449.2多項(xiàng)式時(shí)間變換和NP完全問(wèn)題9.2.1多項(xiàng)式時(shí)間變換定義9.7設(shè)判斷問(wèn)題Ⅱ1=<D1，Y1>，其中D1是該問(wèn)題的實(shí)例集合，由Ⅱ1的所有可能的實(shí)例組成，Y1

D1由所有回答為yes的實(shí)例組成。另外一個(gè)判斷問(wèn)題Ⅱ2=<D2，Y2>同樣類似的描述。如果函數(shù)f：D1→D2滿足以下條件：①f是多項(xiàng)式時(shí)間可計(jì)算的，即存在計(jì)算f的多項(xiàng)式時(shí)間算法。②對(duì)于所有的I∈D1，I∈Y1

f(I)∈Y2。則稱f為Ⅱ1到Ⅱ2的多項(xiàng)式時(shí)間變換。如果存在Ⅱ1到Ⅱ2的多項(xiàng)式時(shí)間變換，則稱Ⅱ1可以多項(xiàng)式時(shí)間變換到Ⅱ2，記為Ⅱ1≤pⅡ2。23/44【例9-3】哈密爾頓問(wèn)題是求無(wú)向圖G=（V，E）中恰好經(jīng)過(guò)每個(gè)頂點(diǎn)（城市）一次最后回到出發(fā)頂點(diǎn)的回路。

哈密爾頓判斷問(wèn)題：圖G中存在恰好經(jīng)過(guò)每個(gè)頂點(diǎn)一次最后回到出發(fā)頂點(diǎn)的回路嗎？

哈密爾頓判斷問(wèn)題表示為HC=<DHC，YHC>，TSP判定問(wèn)題表示為TSP=<DTSP，YTSP>，證明HC≤pTSP。24/44證明證明HC≤pTSP。多項(xiàng)式時(shí)間變換f：對(duì)于HC的每一個(gè)實(shí)例I，I是一個(gè)無(wú)向圖G=（V，E），TSP判定問(wèn)題對(duì)應(yīng)的實(shí)例f(I)定義為G'=（V'，E'），這里V'=V，E'是含|V|個(gè)頂點(diǎn)的完全無(wú)向圖，任意兩個(gè)不同頂點(diǎn)u和v之間的距離為:d(u,v)=若(u,v)∈E2 否則容易證明G中有一個(gè)哈密爾頓回路當(dāng)且僅當(dāng)G'中有一條長(zhǎng)度為|V|的TSP路徑。從而有I∈YHC

f(I)∈YTSP，也就是說(shuō)HC≤pTSP，示例即證。25/4412211111(a)一個(gè)無(wú)向圖G01342(b)一個(gè)帶權(quán)圖G'01342示例26/44定理9.2≤p具有傳遞性，即若有Ⅱ1≤pⅡ2，Ⅱ2≤pⅡ3，則Ⅱ1≤pⅡ3。27/44定理9.3設(shè)Ⅱ1≤pⅡ2，則Ⅱ2∈P類蘊(yùn)涵Ⅱ1∈P類。由此推出，設(shè)Ⅱ1≤pⅡ2，若Ⅱ1是難解問(wèn)題，則Ⅱ2也是難解問(wèn)題。這樣≤p提供了判定問(wèn)題之間的難度比較，如果Ⅱ1≤pⅡ2，則相對(duì)多項(xiàng)式時(shí)間，Ⅱ2不會(huì)比Ⅱ1容易，或者反過(guò)來(lái)說(shuō)，Ⅱ1不會(huì)比Ⅱ2難。28/449.2.2NP完全性及其性質(zhì)定義9.8如果對(duì)所有的Ⅱ'∈NP，Ⅱ'≤pⅡ，則稱Ⅱ的NP難的。如果Ⅱ是NP難的并且Ⅱ∈NP類，則稱Ⅱ是NP完全問(wèn)題（NPC）。NP完全問(wèn)題是NP類的一個(gè)子集，NP難的問(wèn)題不會(huì)比NP類中的任何問(wèn)題容易，因此NP完全問(wèn)題是NP中最難的問(wèn)題。29/44定理9.4如果存在NP難的問(wèn)題Ⅱ∈P類，則P=NP。假設(shè)P≠NP，那么如果Ⅱ是NP難的則ⅡP類。雖然“P=NP?”至今沒(méi)有解決，但人們普遍相信P≠NP，因而NP完全問(wèn)題成為表明一個(gè)問(wèn)題很可能是難解問(wèn)題的有力證據(jù)。NP完全問(wèn)題PNP30/44定理9.5如果存在NP難的問(wèn)題Ⅱ'，使得Ⅱ'≤pⅡ，則Ⅱ是NP難的。該定理提供了證明Ⅱ是NP難的一條捷徑，不再需要把NP類中所有的問(wèn)題多項(xiàng)式時(shí)間變換到Ⅱ，而只需要把一個(gè)已知的NP難問(wèn)題多項(xiàng)式時(shí)間變換到Ⅱ，這樣為了證明Ⅱ是NP完全問(wèn)題，只需要做兩件事：①證明Ⅱ∈NP類。②找到一個(gè)已知的NP完全問(wèn)題Ⅱ'，并證明Ⅱ'≤pⅡ。31/449.2.3第一個(gè)NP完全問(wèn)題在命題邏輯中，給定一個(gè)布爾公式F，如果它是子句的合取，稱為合取范式（CNF）。一個(gè)子句是文字的析取，這里的文字是一個(gè)布爾變?cè)蛘咚姆?，例如，以下布爾公式F1就是一個(gè)合取范式：

F1=(x1∨x2)∧(

x1∨x3∨x4∨

x5)∧(x1∨

x3∨x4)一個(gè)布爾公式的真值賦值是關(guān)于布爾變?cè)囊唤M取值，一個(gè)可滿足的賦值是一個(gè)真值賦值，它使得布爾公式的值為1。如果一個(gè)布爾公式具有可滿足賦值，則稱該公式是可滿足的?？蓾M足性判定問(wèn)題SAT：給定一個(gè)布爾公式F（合取范式），F(xiàn)是可滿足的嗎？例如，上述公式F1，賦值為x1=1，x3=1，其他取0或者1，F(xiàn)1的結(jié)果為1，所以F1是可滿足的。32/44顯然SAT屬于NP類問(wèn)題，因?yàn)槿菀捉⒁粋€(gè)確定性算法來(lái)驗(yàn)證一個(gè)賦值s是否確實(shí)是SAT的一個(gè)可滿足的賦值。Cook-Levin證明了SAT是NP完全問(wèn)題，稱為Cook-Levin定理。33/449.2.4其他NP完全問(wèn)題3CNF指的是布爾公式F中每個(gè)子句都精確地有3個(gè)不同的文字。例如，以下布爾公式F2就是一個(gè)3CNF：F2=(x1∨

x1∨

x2)∧(x3∨x2∨x4)∧(

x1∨

x3∨

x4)3CNF可滿足性判定問(wèn)題3SAT：給定一個(gè)3CNF公式F，F(xiàn)是可滿足的嗎？例如，上述公式F2，賦值為x1=0，x2=1，x3=1，x4=0，F(xiàn)2的結(jié)果為1，所以F2是可滿足的。34/44定理9.63SAT是NP完全問(wèn)題。證明：利用定理9.5證明。證明3SAT∈NP類。如同證明SAT屬于NP類，很容易建立一個(gè)確定性算法來(lái)驗(yàn)證一個(gè)賦值s是否確實(shí)是3SAT的一個(gè)可滿足的賦值。已知SAT是一個(gè)NP完全問(wèn)題，現(xiàn)在證明SAT≤p3SAT。為此按如下步驟構(gòu)造多項(xiàng)式時(shí)間變換f。35/44F1=(x1∨x2)∧(

x1∨x3∨x4∨

x5)∧(x1∨

x3∨x4)y2∧y1∨x1x2y3∧y4∨y6∨y8∨y5∨y7∨x4

x5

x3x4

x1x3x1第一步，對(duì)于任意給定的布爾公式F對(duì)應(yīng)的F1'如下：F1'=y1∧(y1

(y2∨y3))

∧(y2

(x1∨x2))

∧(y3

(y4∧y5))

∧(y4

(

x1∨y6))

∧(y5

(x1∨y7))

∧(y6

(x3∨y8))

∧(y7

(

x3∨x4))

∧(y8

(x4∨

x5))36/44第二步，將F'進(jìn)一步轉(zhuǎn)換為公式F''，使得F''中的每一個(gè)子句精確地有3個(gè)不同的文字。為此引入兩個(gè)輔助變?cè)猵和q。對(duì)公式F'的子句Ci'做如下轉(zhuǎn)換：

①如果Ci'有3個(gè)不同的文字，保持不變。

②如果Ci'有2個(gè)不同的文字，例如l1∨l2，將其轉(zhuǎn)換為(l1∨l2∨p)∧(l1∨l2∨

p)

③如果Ci'僅有1個(gè)文字l，將其轉(zhuǎn)換為(l∨p∨q)∧(l∨p∨

q))∧(l∨

p∨q))∧(l∨

p∨

q)上述轉(zhuǎn)換均是等價(jià)轉(zhuǎn)換，這樣得到3SAT的公式F''，顯然轉(zhuǎn)換過(guò)程是多項(xiàng)式時(shí)間，所以SAT≤p3SAT成立。SAT為NP完全問(wèn)題，所以3SAT也是一個(gè)NP完全問(wèn)題。37/44【例9-4】團(tuán)集判定問(wèn)題CLIQUE是給定一個(gè)無(wú)向圖G=（V，E）和一個(gè)正整數(shù)k，問(wèn)G中有大小為k的團(tuán)集嗎？無(wú)向圖G中大小為k的團(tuán)集是指包含k個(gè)頂點(diǎn)的完全子圖。

證明CLIQUE是NP完全問(wèn)題。38/44證明：利用定理9.5證明。①證明CLIQUE∈NP類。如果s被宣稱為一個(gè)解，則對(duì)應(yīng)一個(gè)大小為k的團(tuán)集V'，只需要看V'中任意兩個(gè)頂點(diǎn)之間是否有邊相連，從而得到了一個(gè)確定性驗(yàn)證算法，所以CLIQUE屬于NP類。39/44②已知3SAT是一個(gè)NP完全問(wèn)題，現(xiàn)在證明3SAT≤pCLIQUE。對(duì)于