13完全性北京大學信息科學技術(shù)

1、算法設計與分析第13講完全性汪小林信息科學技術(shù)學院1主要內(nèi)容7.1 P類與NP類7.1.1 易解的問題與難解的問題7.1.2 判定問題7.1.3 NP類7.2 多項式時間變換與NP完全性7.2.1 多項式時間變換7.2.2 NP完全性7.2.3 Cook-Levin定理第一個NP完全問題7.3 幾個NP完全問題 最大可滿足性與三元可滿足性、頂點覆蓋,團與集、哈密頓回路與貨郎問題、恰好覆蓋、子集和, 背包, 裝箱與雙機調(diào)度7.1 P類與NP類7.1.1 易解的問題與難解的問題評價算法好壞的重要標準運行時間O(nlogn)O(n2)快速排序算法Dijkstra算法O(n2n)最大團問題的回溯法用一

2、臺每秒10億次的超大型計算機計算快速排序算法給10萬個數(shù)據(jù)排序, 運算量約為105log21051.7106, 僅需1.7106/109=1.710-3秒.什么是好算法?Dijkstra算法求解1萬個頂點的圖的單源最短路徑問題,運算量約為(104)2=108, 約需108/109=0.1秒.回溯法解100個頂點的圖的最大團問題, 運算量為10021001.81032, 需要1.81032/109=1.81021秒=5.71015年, 即5千7百萬億年!再從另外一個角度來看1分鐘能解多大的問題. 1分鐘60秒,這臺計算機可做61010次運算, 用快速排序算法可給2109(即, 20億)個數(shù)據(jù)排序

3、, 用Dijkstra算法可解2.4105個頂點的圖的單源最短路徑問題. 而用回溯法一天只能解41個頂點的圖的最大團問題.算法的時間復雜度函數(shù) f 和 g 是多項式相關的: 如果存在多項式 p 和 q 使得, 對任意的nN, f(n)p(q(n) 和g(n)q(f(n).nlogn與n2, n2+2n+5與n10都是多項式相關的,logn與n, n5與2n不是多項式相關的.問題P 的實例I的規(guī)模:I 的二進制編碼的長度, 記作|I|.定義7.1 如果存在函數(shù) f:NN使得, 對任意的規(guī)模為n的實例I, 算法 A對I的運算在 f(n)步內(nèi)停止, 則稱算法A的時間復雜度為f(n).多項式時間算法:

4、 以多項式為時間復雜度. 易解的問題: 有多項式時間算法.難解的問題: 不存在多項式時間算法.例如幾點說明1.當采用合理的編碼時, 輸入的規(guī)模都是多項式相關的.“合理的”是指在編碼中不故意使用許多冗余的字符.例如, 設實例I是一個無向簡單圖G=,V=a.b,c,d, E=(a,b),(a,d),(b,c),(b,d),(c,d).若用鄰接矩陣表示, 則編碼e1=0101/1011/0101/1110/, 長度為20.若用關聯(lián)矩陣表示, 則編碼e2=11000/10110/00101/01011/, 長度為24.設G有n個頂點m條邊, 則用鄰接矩陣時|I|=n(n+1), 矩陣時|I|=n(m+

5、1). 兩者是多項式相關的.用關聯(lián)幾點說明2. 自然數(shù)應采用二 (k2)進制編碼, 不能采用一進制編碼.n的二進制編碼有l(wèi)og2(n+1)位, 一進制編碼有n位, 兩者不是多項式相關的.3. 時間復雜度常表成計算對象的某些自然參數(shù)的函數(shù), 如圖的頂點數(shù)或頂點數(shù)與邊數(shù)的函數(shù).實例的二進制編碼的長度與這些自然參數(shù)通常都是多項 式相關的.4. 關于操作指令集的兩點說明. 運行時間通常是計算執(zhí)行的操作指令數(shù), 這就要求執(zhí)行的指令數(shù)與實際的運行時間是多項式相關的.幾點說明4.1 要求每一條指令的執(zhí)行時間是固定的常數(shù). 例如, 2個不超過計算機字長的二進制數(shù)的四則運算是一條合理的指令. 而2個任意長度的二

6、進制數(shù)的四則運算不能作為合理的指令. 當超過計算機字長時, 必須進行分段處理.4.2 算法的計算步數(shù)與采用的操作指令集有關. 這就要求任何兩個“合理的”操作指令集, 其中一個指令集中的每一條指令都可以用另一個指令集中的指令模擬, 且模擬所用的指令條數(shù)不超過某個固定的常數(shù).可以規(guī)定一個基本操作指令集, 如它由位邏輯運算與、或、非組成, 然后認為任何可以用這個基本操作指令集中常數(shù)條指令實現(xiàn)的操作都是合理的指令, 由有限種合理的指令的操作指令集是合理的操作指令集.幾點說明在上述約定下, 算法是否是多項式時間的與采用的編碼和操作指令集無關, 從而一個問題是易解的、還是難解的也與采用的編碼和操作指令集無

7、關.設有編碼s1,s2和操作指令集 D1,D2. 實例 I 的這兩種編碼的長度分別為|I|1和|I|2. 存在多項式 p和 q, 使得 |I|1p(|I|2) 和 |I|2q(|I|1). 又存在常數(shù) k1和 k2, 使得D1(D2)中的每一條指令都可以用 D2(D1)中的不超過 k1 (k2)條指令模擬.設算法 A在采用編碼s1和操作指令集 D1時存在多項式 f 使得, 對任意的實例I, 算法在 f(|I|1)步內(nèi)停機. 不妨設 f 是單調(diào)遞增的. 若采用操作指令集D2, 算法至多運行 k1 f(|I|1) k1 f(p(|I|2)步. 故 A在采用編碼 s2 和操作指令集 D2 時也是多項

8、式時間的. 反之亦然.易解的問題與難解的問題易解的問題. 如排序、最小生成樹、單源最短路徑等已證明的難解問題. 一類是不可計算的, 即根本不存在求解的算法, 如希爾伯特第十問題丟番圖方程是否有整數(shù)解.另一類是有算法, 但至少需要指數(shù)時間, 或指數(shù)空間, 甚的時間或更大的空間. 如帶冪運算的正則表達式的至全體性, 即任給字母表 A上的帶冪運算的正則表達式R, 問:R=A*?這個問題至少需要指數(shù)空間.既沒有找到多項式時間算法、又沒能證明是難解的問題. 如哈密頓回路問題、貨郎問題、背包問題等7.1.2 判定問題只有兩個是, 否.判定問題:判定問題 P = , 其中DP 是實例集合, YP DP 是為

9、“Yes”的實例.所有哈密頓回路(HC): 任給無向圖G, 問G有哈密頓回路嗎?貨郎問題(TSP): 任給n個城市, 城市i與城市j之間的正整數(shù)距離 d(i,j), ij, 1i, jn, 以及正整數(shù)D, 問有一條每一個城市恰好經(jīng)過一次最后回到出發(fā)點且長度不超過D的巡回路線嗎? 即, 存在1,2,n的排列s 使得n-1 d (s (i),s (i + 1) + d (s (n),s (1) D ?i =1組合優(yōu)化問題與判定問題0-1背包: 任給n件物品和一個背包, 物品i的重量為wi, 價值為vi, 1in, 以及背包的重量限制B和價值目標K, 其中wi, vi, B, K均為正整數(shù), 問能在

10、背包中裝入總價值不少于K且總重量不超過B的物品嗎?即, 存在子集T1,2,n使得wi Bvi K ?且iTiT搜索問題, 組合優(yōu)化問題與判定問題的對應.如果搜索問題, 組合優(yōu)化問題有多項式時間算法, 則對應的判定問題也有多項式時間算法; 通常反之亦真.組合優(yōu)化問題與判定問題組合優(yōu)化問題P*由3部分組成:(1) 實例集DP*,;(2) IDP*, 有一個有窮非空集S(I), 其元素稱作I的可行解.(3) sS(I), 有一個正整數(shù)c(s), 稱作s的值.如果s*S(I), 對所有的sS(I), 當P*是最小(大)化問題時,c(s*)c(s)(c(s*)c(s)則稱s*是I的最優(yōu)解, c(s*)是

11、I的最優(yōu)值, 記作OPT(I).P*對應的判定問題P =定義如下: DP=(I,K) | IDP*,KZ*, 其中Z*是非負整數(shù)集合. 當P*是最小化問題時, YP=(I,K) | OPT(I)K;當P*是最大化問題時, YP=(I,K) | OPT(I)K.7.1.3NP類定義7.2 所有多項式時間可解的判定問題組成的問題類稱作P類.定義7.3 設判定問題P =, 如果存在兩個輸入變量的多項式時間算法 A和多項式 p, 對每一個實例 ID, IY 當且僅當存在 t, |t| p(|I|), 且 A對輸入 I 和 t 輸出“Yes”, 則稱P 是多項式時間可驗證的,A是P 的多項式時間驗證算法

12、, 而當IY時, 稱 t是IY的證據(jù).由所有多項式時間可驗證的判定問題組成的問題類稱作NP類.例如,HC, TSP, 0-1背包NP非確定型多項式時間算法非確定型多項式時間算法:對給定的實例 I, 首先“猜想”一個 t,|t| p(|I|), 然后檢查t 是否是證明 IY 的證據(jù), 猜想和檢查可以在多項式時間內(nèi)完成, 并且當且僅當t.IY 時能夠正確地猜想到一個證據(jù)定理7.1 PNP.問題: P=NP?7.2 多項式時間變換與NP完全性7.2.1 多項式時間變換如何比較兩個問題的難度?定義7.4 設判定問題P1=, P2=. 如果函數(shù)f:D1 D2滿足條件:(1) f 是多項式時間可計算的,(

13、2) 對所有的ID1, IY1f(I)Y2,則稱 f 是P1到P2的多項式時間變換.如果存在P1到P2的多項式時間變換, 則稱P1可多項式時間變換到P2, 記作P1pP2.例例7.1HCpTSP.證 對HC的每一個實例I: 無向圖G=, TSP對應的實例f(I)為: 城市集V, 任意兩個不同的城市u和v之間的距離d (u, v) = 1,若(u, v) E,否則,2,以及界限D(zhuǎn)=|V|.例最小生成樹: 任給連通的無向賦權(quán)圖G=以及正整數(shù)B, 其中權(quán)W:EZ+, 問不超過B的生成樹嗎?最大生成樹: 任給連通的無向賦權(quán)圖G=以及正整數(shù)D, 其中權(quán)W:EZ+, 問G不小于D的生成樹嗎?例7.2 最大

14、生成樹p最小生成樹.證 任給最大生成樹的實例I:連通的無向賦權(quán)圖G=和正整數(shù)D, 最小生成樹的對應實例f(I): 圖G=和正整數(shù)B=(n-1)M-D, 其中n=|V|, M=maxW(e) | eE+1, W (e)=M-W(e). 如果存在G的生成樹T, 使得, 則W (e) DeTW (e) = (n - 1)M - W (e) (n - 1)M - D = B.eTeT反之亦然.p的性質(zhì)定理7.2p具有傳遞性. 即, 設P1pP2, P2pP3, 則P1pP3. 證 設Pi=, i=1,2,3, f和g是P1到P2和P2到P3的多項式時間變換.對每一個ID1, 令h(I)=g(f(I).

15、計算f和g的時間上界分別為多項式p和q, 不妨設p和q是單調(diào)遞增的. 計算h的步數(shù)不超過p(|I|)+ q(|f(I)|). 輸出作為合理的指令, 一步只能輸出長度不超過固定值k的字符串, 因而|f(I)|kp(|I|). 于是, p(|I|)+ q(|f(I)|) p(|I|)+q(kp(|I|), 得證h 是多項式時間可計算的.又, 對每一個ID1,IY1 f(I)Y2 h(I) =g(f(I)Y3,得證h是P1到P3的多項式時間變換.p的性質(zhì)定理7.3 設P1pP2, 則P2P 蘊涵 P1P.證 設P1=, P2=, f是P1到P2的多項式時間變換, A是計算f的多項式時間算法. 又設B

16、是P2的多項式時間算法. 如下構(gòu)造P1的算法C: 對每一個ID1, 首先應用A得到f(I), 然后對f(I)應用B, C輸出“Yes”當且僅當B輸出“Yes”.推論7.4設P1pP2, 則P1是難解的蘊涵P2是難解的. 由例7.2及最小生成樹P, 得知最大生成樹P.由例7.1, 如果TSPP, 則HCP. 反過來, 如果HC是難解的,則TSP也是難解的.7.2.2 NP完全性定義7.5 如果對所有的PNP, P p P, 則稱P 是NP難的.如果P 是NP難的且PNP, 則稱P 是NP完全的.NP完全問題是NP中最難的問題.定理7.5 如果存在NP難的問題PP, 則P=NP.推論7.6 假設P

17、NP, 那么, 如果P 是NP難的, 則PP.定理7.7 如果存在NP難的問題P 使得 P p P, 則P 是NP 難的.推論7.8 如果PNP并且存在NP完全問題P 使得 P p P,則P 是NP完全的.證明NP完全性的“捷徑”為了證明P 是NP完全的, 只需要做兩件事:(1) 證明PNP;(2) 找到一個已知的NP完全問題P , 并證明P p P.7.2.3 Cook-Levin定理合式公式是由變元,邏輯運算符以及圓括號按照一定的規(guī)則組成的表達式. 變元和它的稱作文字. 有限個文字的析取稱作簡單析取式. 有限個簡單析取式的合取稱作合取范式.給定每一個變元的真假值稱作一個賦值. 如果賦值t使

18、得合式公式F為真, 則稱t是F的成真賦值. 如果F存在成真賦值, 則稱F是可滿足的.F1=( x1 x2)( x1 x2 x3) x2是一個合取范式.例如令t(x1)=1, t(x2)=0, t(x3)=1是F1的成真賦值,F1是可滿足的.F2=( x1 x2 x3)( x1 x2 x3) x2 x3不是可滿足的.Cook-Levin定理可滿足性(SAT): 任給一個合取范式F, 問F是可滿足的嗎?定理7.9 (Cook-Levin定理) SAT是NP完全的.定理7.10P=NP的充分必要條件是存在NP完全問題PP.7.3 幾個NP完全問題SAT恰好覆蓋3SAT最大可滿足性子集和VC有向HCH

19、C雙機調(diào)度背包集裝箱團7.3.1 最大可滿足性與三元可滿足性最大可滿足性(MAX-SAT): 任給關于變元x1, x2, xn的簡單析取式C1,C2,Cm及正整數(shù)K, 問存在關于變元x1, x2, xn的賦值使得C1,C2,Cm中至少有K個為真嗎?設判定問題P =, P =, 如果DD, Y = DY, 則P 是P 的特殊情況, 稱作P 的子問題.例如“給定一個平面圖G, 問G是哈密頓圖嗎?”是HC的子問題.SAT是MAX-SAT的子問題:取K=m.MAX-SAT: 如果已知P 的某個子問題P 是NP難的, 則P 也是NP限比特殊情況容易. 容易把P 多項式時難的一般情況間變換到P : 只需把

20、P 的實例I看作P特殊情況的實例, 即可得到P 對應的實例.定理7.11MAX-SAT是NP完全的.證 MAX-SAT的非多項式時間算法: 猜想一個賦值, 檢查是否有K個簡單析取式滿足.要證SATpMAX-SAT. 任給SAT的實例I: 關于變元x1, x2,xn的合取范式F=C1C2Cm, 其中C1,C2,Cm是簡單析取式, 對應的MAX-SAT的實例f(I): 簡單析取式C1,C2,Cm和正整數(shù)K=m.3SAT3元合取范式: 每一個簡單析取式恰好有3個文字的合取范式. 三元可滿足性(3SAT): 任給一個3元合取范式F, 問F是可滿足的嗎?定理7.123SAT是NP完全的.顯然 3SATN

21、P.證要證 SAT p3SAT. 任給一個合取范式F, 要構(gòu)造對應的 3元合取范式F = f(F), 使得F是可滿足的當且僅當F 是可滿足的.設F =C1C2Cm , 對應的F =F1F2 Fm,Fj 是 對應Cj 的合取范式, 并且Cj是可滿足的當且僅當 Fj是可滿足的.證明(1) Cj=z1. 引入兩個新變元yj1, yj2, 令Fj =(z1 yj1 yj2)(z1 yj1 yj2)(z1 yj1 yj2)(z1 yj1 yj2).(2) Cj=z1z2. 引入一個新變元yj, 令Fj = (z1 z2 yj)(z1 z2 yj).(3) Cj=z1z2z3. 令 Fj = Cj.(4)

22、 Cj=z1z2zk, k4. 引入k-3個新變元yj1, yj2,yj(k-3), 令Fj =(z1 z2 yj1)( yj1 z3 yj2) ( yj2 z4 yj3)( yj(k-4) zk-2 yj(k-3) ( yj(k-3) zk-1 zk). 設賦值 t 滿足Cj, 則存在i使得 t(zi)=1. 當i=1或2時, 令t(yjs)=0 (1sk-3); 當i=k-1或k時, 令t(yjs)=1 (1sk-3); 當3ik-2時, 令t(yjs)=1(1si-2), t(yjs)=0(i-1sk-3). 則有,t(Fj )=1.證明反之, 設t(Fj)=1. 若t(yj1)=0,

23、則 t(z1 z2)=1; 若t(yj(k-3)=1, 則 t(zk-1zk)=1; 否則必有s(1sk-4)使得 t(yjs)=1且 t(yj(s+1)=0, 從而t(zs+2)=1. 總之, 都有t(Cj)=1.Fj 中簡單析取式的個數(shù)不超過Cj中文字個數(shù)的4倍, 每個簡單析取式有3個文字, 因此可以在|F|的多項式時間內(nèi)構(gòu)造出F.局部替換法 要證P1pP2. 當P2是P1的子問題或兩者的結(jié)構(gòu)相似時, 往往可以把P1的實例的每一個子結(jié)構(gòu)替換成對應的P2實例的子結(jié)構(gòu).7.3.2 頂點覆蓋、團與設無向圖G=, V V. V 是G的一個頂點覆蓋: G的每一條邊都至少有一個頂點在V 中.團: 對任

24、意的u,vV 且uv, 都有(u,v)E.集: 對任意的u,vV , 都有(u,v)E.集引理7.13 對任意的無向圖G=和子集V V, 下述命題是等價的:(1) V 是G的頂點覆蓋,(2) V-V 是G的集,(3) V-V 是補圖 Gc=的團.頂點覆蓋、團與集頂點覆蓋(VC): 任給一個無向圖G=和非負整數(shù)K|V|,問G有頂點數(shù)不超過K的頂點覆蓋嗎?團: 任給一個無向圖G=和非負整數(shù)J|V|, 問G有頂點數(shù)不小于J的團嗎?集: 任給一個無向圖G=和非負整數(shù)J|V|, 問G有頂點數(shù)不小于J的集嗎?根據(jù)引理7.13, 很容易把這3個問題中的一個問題多項式時間變換到另一個問題.頂點覆蓋定理7.14

25、 頂點覆蓋是NP完全的.證: VC的非確定型多項式時間算法: 任意猜想一個子集VV, |V |K, 檢查V 是否是一個頂點覆蓋.要證3SATpVC. 任給變元x1, x2, xn的3元合取范式F=C1C2Cm, 其中Cj=zj1 zj2 zj3, zjk是某個xi或xi.如下構(gòu)造VC的實例f(F):G=和K=n+2m, 其中V=V1V2,E=E1E2E3 ,V1= xi,xf| 1iniE1=( xi,xf )| 1ini證明V2=zjk, j| k=1,2,3, 1jm,E2=(zj1, j,zj2, j), (zj2, j,zj3, j), (zj3, j,zj1, j)| 1jm.E3=

26、(zjk, j, zjk )| k=1,2,3, 1jm這里設Cj=zj1 zj2 zj3, 當zjk=xi時, zjk =xi; 當zjk= xi時, zjk =xf .i例如, 對應F=(x1x2x3)(x1x2x3)的f(F):K=7, 圖G如下x1xfxxfxxf12233x2, 2xf , 12xf , 33x1, 1x3, 1x1, 2證明要證F是可滿足的G恰好有K個頂點的頂點覆蓋.任何頂點覆蓋V 在xi和xf中至少取一個, 在z ,j、z,j和ij1j2zj3 ,j中至少取2個,故V 至少有n+2m個頂點. 而K=n+2m, 故任何頂點數(shù)不超過K的頂點覆蓋V 恰好包含K個頂點,

27、且在xi和 xf 中取一個, 這恰好對應對x 的賦值, 取x 對應t(x )=1,取xfiiiii對應t(xi)=0; 每個三角形的頂點zj1,j、zj2,j和zj3,j中取2個.設t是F的成真賦值, 對每一個i(1in), 若t(xi)=1, 則取xi; 若t(xi)=0, 則取xfi . 這n個頂點覆蓋E1. 對每一個j(1jm), 由于t(Cj)=1, Cj至少有一個文字zjk的值為1. 于是, 從對應的三角形的頂點zjk,j引出的邊(zjk,j, zjk )已被覆蓋. 取該三角形的另外2個頂點, 這就覆蓋了這個三角形的3條邊和引出的另外2條邊. 這樣取到的n+2m個頂點是G的一個頂點覆

28、蓋.證明反之, 設V V是G的一個頂點覆蓋且| V |K=n+2m. 根據(jù)前面的分析, 每一對xi和 xf 中恰好有一個屬于V, 每一個三角形恰i好有2個頂點屬于V. 對每一個i(1in), 若xiV, 則令t(xi)=1;若 xf V, 則令t(x )=0. 對每一個j(1jm), 設z ,jV, 為了覆iijk蓋邊(zjk,j, zjk ), 必有 zjkV. 由于t(zjk)=1, 從而t(Cj)=1. 因此, t是F的成真賦值, 得證F是可滿足的.G有2n+3m個頂點和n+6m條邊, 顯然能在多項式時間內(nèi)構(gòu)造G和K,定理7.15集和團是NP完全的.構(gòu)件設計法構(gòu)件設計法 定理7.14證明

29、中設計了2種“構(gòu)件” 變元構(gòu)件和簡單析取式構(gòu)件. 變元構(gòu)件是一對頂點xi, xf及連接它們i的邊; 簡單析取式構(gòu)件是三角形. 用這些構(gòu)件及構(gòu)件之間的連G, 每個構(gòu)件各有其功能, 通過這種方式到達用VC的實接例表達3SAT的實例的目的.7.3.3 哈密頓回路與貨郎問題有向哈密頓回路: 任給有向圖D, 問:D中有哈密頓回路嗎? 定理7.16 有向HC是NP完全的.證 要證3SATp有向HC. 任給變元x1, x2, xn的3元合取范式F=C1C2Cm, 其中Cj=zj1 zj2 zj3, 每個zjk是某個xi或xi.采用構(gòu)件設計法構(gòu)造有向圖D. 表示變元xi的構(gòu)件是一條由一串水平的頂點組成的鏈Li

30、, 相鄰的兩個頂點之間有一對方向相反的有向邊. 只有兩種可能的方式通過Li上的所有頂點從左到右或者從右到左通過Li上的所有頂點, 這恰好對應xi的值為1或者為0. 表示簡單析取式Cj的構(gòu)件是一個頂點cj.添加s0, s1, xn, 并通過它們把L1, L2, Ln連接起來.證明關鍵是兩種構(gòu)件之間的連接: 鏈Li有3m+1的頂點, 依次為di0, ai1, bi1, di1, ai2, bi2, di2, , aim, bim, dim. 對每一個Cj=zj1 zj2 zj3, 如果zjk=xi, 則添加和; 如果zjk=xi, 則添加 和.例如 C2=x1x3x4對應的連接證明設F是可滿足的,

31、 t是F的成真賦值. 要根據(jù)t構(gòu)造一條從s0到sn, 最后回到s0的哈密頓回路, 先暫時不考慮所有的cj.依次對i=1,2,n進行, 若t(xi)=1, 則從si-1到di0, 從左到右經(jīng)過Li的所有頂點到達dim, 再到si; 若t(xi)=0, 則從si-1到dim, 從右到左經(jīng)過Li 的所有頂點到達di0, 再到si. 最后, 從sn回到s0. 現(xiàn)在要將所有cj這條回路. 設Cj=zj1 zj2 zj3, 由于t(Cj)=1, 必有k(1k3)使得t(zjk)=1. 若zjk =xi, 則通路從左到右經(jīng)過Li, 且有有向邊和. 于是, 可以把cj插在aij與bij之間; 若zjk = x

32、i,則通路從右到左經(jīng)過Li, 且有有向邊和. 于是, 可以把cj插在bij與aij之間. 這就得到D中的一條哈密頓回路.證明反之, 設D有一條哈密頓回路P, P必須從sn到s0. 不妨設P從s0 開始到sn, 最后回到s0結(jié)束. 我們稱上面構(gòu)造的那種哈密頓回路是正常的, 即正常的回路從左到右或者從右到左通過每一條Li, 每一個cj插在某個aij和bij或者bij和aij之間. 如果P是正常的, 容易根據(jù)P規(guī)定F的一個成真賦值t: 若P從左到右通過Li,則令t(xi)=1; 若P從右到左通過Li, 則令t(xi)=0. 根據(jù)cj方式, 不難證明必有t(Cj)=1.Li的要證P一定是正常的. 假設

33、不然, 破壞正常性的惟一可能是P從某條鏈Ls上的頂點u到cj后沒有回到同一條鏈中的頂點, 而是到另一條鏈Lt(st)中的頂點. 若u=asj, 由于bsj只與asj、 cj及dsj證明相鄰, P已經(jīng)過asj和cHC與TSP定理7.17HC是NP完全的.證 要證有向HC p HC. 任給一個有向圖D=, 要構(gòu)造無向圖G=使D有哈密頓回路當且僅當G有哈密頓回路.把D的每一個頂點v替換成3個頂點vin, vmid和vout, 用邊連接vin和vmid, vmid和vout. D的每條有向邊在G中換成( uout, vin).V = vin, vmid, vout | vV ,E =( uout, v

34、in) | E(vin,vmid),( vmid,vout) | vV .即定理17.18TSP是NP完全的.7.3.4 恰好覆蓋恰好覆蓋: 給定有窮集A=a1, a2, an和A的子集的集合W=S1, S2, S m, 問: 存在子集UW使得U中的子集都是不相交的且它們的并集等于A? 稱W這樣的子集U是A的恰好覆蓋. 例如, 設A=1,2,3,4,5, S1=1,2, S2=1,3,4, S3=2,4, S4=2,5,則 S2, S4是A的恰好覆蓋. 若把S4改為S4=3,5, 則不存在A的恰好覆蓋.定理7.19 恰好覆蓋是NP完全的.證明證 要證可滿足性p恰好覆蓋. 任給變元x1, x2,

35、 xn的合取范式F=C1C2Cm, 其中 Cj= z j1 z j 2 L, z js. 取jA=x1, x2, xn,C1,C2,Cm pjt | 1tsj, 1jm,其中pjt代表Cj中的文字zjt.W包含下述子集:TT = x , p | z =x , 1ts , 1jm,1in,iijtjtijTF = x , p | z =x , 1ts , 1jm,1in,iijtjtijCjt =Cj, pjt, 1tsj, 1jm. pjt , 1tsj, 1jm.要證F是可滿足的當且僅當W含有A的恰好覆蓋. 設UW是A的恰好覆蓋, 對每一個i, 若 TTi U, 則令t(xi)=1;若TF

36、U, 則令it(xi)=0. 對每一個j, 必有一個Cjt=Cj, pjtU.zjt=xi或xi . 若TTU, 則pjtTT, 從而z =x . 有t(x )=1, 故t滿足C .iijtiij證明若TFiU, 則pjtTFi , 從而zjt =xi. 有t(xi)=0, 故t也滿足Cj. 得證t是F的成真賦值.反之, 設t是F的成真賦值. 對每一個i, 若t(xi)=1, 則U包含TTi; 若t(xi)=0, 則U包含TFi . 對每一個j, 由于t滿足Cj, Cj必有一個文字zjt使得t(zjt)=1, 從而U中現(xiàn)有的子集不包含pjt. 于是, 可以把Cjt加入U. 至此, U覆蓋了所有

37、的xi和Cj, 以及部分pjt. 最后, 把那些尚未被覆蓋的pjt的恰好覆蓋.的單元子集pjt加入U, 即可得到A由于F中的文字數(shù)不超過mn, 故|A|n+m+mn, W中的子集數(shù)不超過2n+2mn, 每個子集的大小不超過n+1.而且構(gòu)造很簡單, 顯然可以在多項式時間內(nèi)完成.7.3.5 子集和,背包,裝箱與雙機調(diào)度子集和: 給定正整數(shù)集合X=x1, x2, xn及正整數(shù)N, 問存在X的子集T, 使得T中的元和等于N嗎?裝箱: 給定n件物品, 物品j的重量為正整數(shù)wj, 1jn, 以及箱子數(shù)K. 規(guī)定每只箱子裝入物品的總重量不超過正整數(shù)B, 問能用K只箱子裝入所有的物品嗎?雙機調(diào)度: 有2臺和n項作業(yè)J1, J2, Jn, 這2臺完全相同, 每一項作業(yè)可以在任一臺上進行, 沒有先后順序,作業(yè)Ji的處理時間為ti, 1in, 截止時間為D, 所有ti和D都是正整數(shù), 問能把n項作業(yè)分