第8章 NP完全性理論算法設計與分析8.1 計算模型8.1.1隨機存取機RAM8.1.2隨機存取存儲程序機RASP8.1.3RAM模型的變形與簡化8.1.4圖靈機8.1.5圖靈機模型與RAM模型的關系8.1.6問題變換與計算復雜性歸約2算法設計與分析8.1.1隨機存取機RAM1、RAM的結構3算法設計與分析8.1.1隨機存取機RAM2、RAM程序

一個RAM程序定義了從輸入帶到輸出帶的一個映射。可以對這種映射關系作2種不同的解釋。解釋一：把RAM程序看成是計算一個函數 若一個RAM程序P總是從輸入帶前n個方格中讀入n個整數x1，x2，…，xn，并且在輸出帶的第一個方格上輸出一個整數y后停機，那么就說程序P計算了函數f(x1，x2，…，xn)=y解釋二：把RAM程序當作一個語言接受器。 將字符串S=a1a2…an放在輸入帶上。在輸入帶的第一個方格中放入符號a1，第二個方格中放入符號a2，…，第n個方格中放入符號an。然后在第n+1個方格中放入0，作為輸入串的結束標志符。如果一個RAM程序P讀了字符串S及結束標志符0后，在輸出帶的第一格輸出一個1并停機，就說程序P接受字符串S。4算法設計與分析8.1.1隨機存取機RAM3、RAM程序的耗費標準標準一：均勻耗費標準 在均勻耗費標準下，每條RAM指令需要一個單位時間；每個寄存器占用一個單位空間。以后除特別注明，RAM程序的復雜性將按照均勻耗費標準衡量。標準二：對數耗費標準 對數耗費標準是基于這樣的假定，即執(zhí)行一條指令的耗費與以二進制表示的指令的操作數長度成比例。在RAM計算模型下，假定一個寄存器可存放一個任意大小的整數。因此若設l(i)是整數i所占的二進制位數，則5算法設計與分析8.1.2隨機存取存儲程序機RASP1、RASP的結構 RASP的整體結構類似于RAM，所不同的是RASP的程序是存儲在寄存器中的。每條RASP指令占據2個連續(xù)的寄存器。第一個寄存器存放操作碼的編碼，第二個寄存器存放地址。RASP指令用整數進行編碼。2、RASP程序的復雜性

不管是在均勻耗費標準下，還是在對數耗費標準下，RAM程序和RASP程序的復雜性只差一個常數因子。在一個計算模型下T(n)時間內完成的輸入-輸出映射可在另一個計算模型下模擬，并在kT(n)時間內完成。其中k是一個常數因子。空間復雜性的情況也是類似的。6算法設計與分析8.1.3RAM模型的變形與簡化1、實隨機存取機

RRAM在RRAM模型下，一個存儲單元可以存放一個實數。下列的各運算為基本運算且每個運算只耗費單位時間。(1)算術運算+，－，×，／。(2)2個實數間的比較(<，≤，=，≠，≥，>)。(3)間接尋址(整數地址)。(4)常見函數的計算，如三角函數，指數函數，對數函數等。優(yōu)點：能夠方便處理實數；

適合于用FORTRAN，PASCAL等高級語言寫的算法。7算法設計與分析8.1.3RAM模型的變形與簡化2、直線式程序 對于許多問題，所設計的RAM程序中的轉移指令僅用于重復一組指令，而且重復的次數與問題的輸入規(guī)模n成比例。在這種情況下，可以用重復地寫出相同指令組的方法來消除程序中的循環(huán)。由此，對每一個固定的n得到一個無循環(huán)的直線式程序。經過對RAM模型的簡化，得到直線式程序的指令系統(tǒng)如下：x←y+zx←y-zx←y*zx←y/zx←i其中x，y和z是符號地址(或變量)，而i是常數。每條指令耗費一個單位時間。8算法設計與分析8.1.3RAM模型的變形與簡化3、位式計算 直線式程序計算模型顯然是基于均勻耗費標準的。在對數耗費標準下，使用另一個RAM的簡化計算模型，稱之為位式計算(BitwiseComputation)模型。 除了下列2點外，該計算模型與直線式程序計算模型基本相同：(1)假設所有變量取值0或1，即為位變量。(2)所用的運算是邏輯運算而不是算術運算。 用∧代表與，∨代表或，代表異或，代表非。在位式計算模型下，每個邏輯運算指令耗費一個單位時間。

9算法設計與分析8.1.3RAM模型的變形與簡化4、位向量運算(BitVectorOperations)若在直線式程序計算模型中，假設所有變量均為位向量，而且所用的運算均為位操作指令，則得到位向量運算計算模型。例如，要表示一個有100個頂點的圖中從頂點v到其余各頂點間有沒有邊相連，可以用100位的一個位向量表示。若頂點v到頂點vj之間有邊相連，則該位向量的第j位為1，否則為0。缺點：所需的機器字長要遠大于其它模型。

10算法設計與分析8.1.3RAM模型的變形與簡化5、判定樹判定樹是一棵二叉樹。它的每個內結點表示一個形如x∶y的比較。指向該結點左兒子的邊相應于x≤y，標號為≤。指向該結點右兒子的邊相應于x>y，標號為>。每一次比較耗費一個單位時間。下圖是對a，b，c三個數進行排序的一棵判定樹。在判定樹模型下，算法的時間復雜性可用判定樹的高度衡量。最大的比較次數是從根到葉的最長路徑的長度。11算法設計與分析8.1.3RAM模型的變形與簡化6、代數計算樹ACT 以x=(x1，x2，…，xn)為輸入的一棵代數計算樹T是一棵二叉樹，且：(1)每個葉結點表示一個輸出結果YES或NO。(2)每個單兒子內部結點(簡單結點)v表示下列形式運算指令：

op或op或其中，和分別是結點v在樹T中的祖先結點v1和v2處得到的結果值，或是x的分量；op∈{+，－，×，/}；c是一個常數。(3)每個有2個兒子的內部結點(分支結點)v，表示下列形式的測試指令：>0或≥0或=0其中，是結點v在樹T中的祖先結點v1處得到的結果值，或是x的分量。12算法設計與分析8.1.3RAM模型的變形與簡化7、代數判定樹ADT(AlgebraicDecisionTree)

在代數計算樹T中，若將所有的簡單結點都壓縮到其最近的子孫分支結點處，并將簡單結點處的計算在壓縮后的分支結點處同時完成，則計算結果可看作是輸入x的一個代數函數fv(x)。由此引出另一個稱為代數判定樹的計算模型。代數判定樹T是一棵二叉樹，且(1)每個葉結點表示輸出結果YES或NO。(2)每個內部結點v表示一個形如fv(x1，x2，…，xn)∶0的比較。其中，x=(x1，x2，…，xn)是輸入，fv是一個代數函數。13算法設計與分析8.1.4圖靈機1、多帶圖靈機14算法設計與分析8.1.4圖靈機1、多帶圖靈機根據有限狀態(tài)控制器的當前狀態(tài)及每個讀寫頭讀到的帶符號，圖靈機的一個計算步可實現(xiàn)下面3個操作之一或全部。(1)改變有限狀態(tài)控制器中的狀態(tài)。(2)清除當前讀寫頭下的方格中原有帶符號并寫上新的帶符號。(3)獨立地將任何一個或所有讀寫頭，向左移動一個方格(L)或向右移動一個方格(R)或停在當前單元不動(S)。

k帶圖靈機可形式化地描述為一個7元組(Q，T，I，δ，b，q0，qf)，其中:(1)Q是有限個狀態(tài)的集合。 (2)T是有限個帶符號的集合。(3)I是輸入符號的集合，IT。(4)b是唯一的空白符，b∈T-I。(5)q0是初始狀態(tài)。 (6)qf是終止(或接受)狀態(tài)。(7)δ是移動函數。它是從QTk的某一子集映射到Q(T{L，R，S})k的函數。15算法設計與分析8.1.4圖靈機1、多帶圖靈機 圖靈機M的時間復雜性T(n)是它處理所有長度為n的輸入所需的最大計算步數。如果對某個長度為n的輸入，圖靈機不停機，T(n)對這個n值無定義。 圖靈機的空間復雜性S(n)是它處理所有長度為n的輸入時，在k條帶上所使用過的方格數的總和。如果某個讀寫頭無限地向右移動而不停機，S(n)也無定義。 與RAM模型類似，圖靈機既可作為語言接受器，也可作為計算函數的裝置。16算法設計與分析8.1.5圖靈機模型與RAM模型的關系 圖靈機模型與RAM模型的關系是指同一問題在這2種不同計算模型下的復雜性之間的關系。

定理8-3對于問題P的任何長度為n的輸入，設求解問題P的算法A在k帶圖靈機模型TM下的時間復雜性為，那么，算法A在RAM模型下的時間復雜性為。 定理8-4對于問題P的任何長度為n的輸入，設求解問題P的算法A在RAM模型下，不含有乘法和除法指令，且按對數耗費標準其時間復雜性為，那么，算法A在k帶圖靈機模型TM下的時間復雜性為。

17算法設計與分析8.1.6問題變換與計算復雜性歸約具體地說，假設有2個問題A和B，將問題A變換為問題B是指：(1)將問題A的輸入變換為問題B的適當輸入。(2)解出問題B。(3)把問題B的輸出變換為問題A的正確解。若用O(τ(n))時間能完成上述變換的第(1)步和第(3)步，則稱問題A是τ(n)時間可變換到問題B，且簡記為A∝τ(n)B。其中的n通常為問題A的規(guī)模(大小)。當τ(n)為n的多項式時，稱問題A可在多項式時間內變換為問題B。特別地，當τ(n)為n的線性函數時，稱問題A可線性地變換為問題B。 通過問題變換的技巧，可以將2個不同問題的計算復雜性聯(lián)系在一起。這樣就可以將一個問題的計算復雜性歸結為另一個問題的計算復雜性，從而實現(xiàn)問題的計算復雜性歸約。18算法設計與分析8.1.6問題變換與計算復雜性歸約

命題1(計算時間下界歸約)：若已知問題A的計算時間下界為T(n)，且問題A是τ(n)可變換到問題B，即A∝τ(n)B，則T(n)-O(τ(n))為問題B的一個計算時間下界。

命題2(計算時間上界歸約)：若已知問題B的計算時間上界為T(n)，且問題A是τ(n)可變換到問題B，即A∝τ(n)B，則T(n)+O(τ(n))是問題A的一個計算時間上界。 問題的變換與問題的計算復雜性歸約的關系： 在命題1和命題2中，當τ(n)=o(T(n))時，問題A的下界歸約為問題B的下界，問題B的上界歸約為問題A的上界。19算法設計與分析8.1.6問題變換與計算復雜性歸約通過問題變換獲得問題的計算時間下界的例子： (1)判別函數問題：給定n個實數，計算其判別函數。

元素唯一性問題可以在O(1)時間內變換為判別函數問題。任何一個計算判別函數的算法，計算出判別函數值后，再作一次測試，判斷其值是否為0，即可得到元素唯一性問題的解。由命題1即知，元素唯一性問題的計算時間下界也是判別函數問題的一個計算時間下界。 (2)最接近點對問題：給定平面上n個點，找出這n個點中距離最近的2個點。 在元素唯一性問題中，將每一個實數，1≤i≤n，變換為平面上的點(，0)，1≤i≤n，則元素唯一性問題可以在線性時間內變換為最接近點對問題。20算法設計與分析8.2 P類與NP類問題8.2.1非確定性圖靈機8.2.2P類與NP類語言8.2.3多項式時間驗證21算法設計與分析8.2.1非確定性圖靈機

非確定性圖靈機（NDTM）：一個k帶的非確定性圖靈機M是一個7元組：(Q，T，I，δ，b，q0，qf)。與確定性圖靈機不同的是非確定性圖靈機允許移動函數δ具有不確定性，即對于QTk中的每一個值(q;x1,x2,…,xk)，當它屬于δ的定義域時，Q(T{L，R，S})k中有唯一的一個子集δ(q;x1,x2,…,xk)與之對應?？梢栽讦?q;x1,x2,…,xk)中隨意選定一個值作為它的函數值。 在圖靈機計算模型中，移動函數δ是單值的，即對于QTk中的每一個值，當它屬于δ的定義域時，Q(T{L，R，S})k中只有唯一的值與之對應，稱這種圖靈機為確定性圖靈機，簡記為DTM(DeterministicTuringMachine)。22算法設計與分析8.2.2P類與NP類語言

P類和NP類語言的定義：P={L|L是一個能在多項式時間內被一臺DTM所接受的語言}NP={L|L是一個能在多項式時間內被一臺NDTM所接受的語言}

由于一臺確定性圖靈機可看作是非確定性圖靈機的特例，所以可在多項式時間內被確定性圖靈機接受的語言也可在多項式時間內被非確定性圖靈機接受。故PNP。

23算法設計與分析8.2.2P類與NP類語言

NP類語言舉例——無向圖的團問題。該問題的輸入是一個有n個頂點的無向圖G=(V，E)和一個整數k。要求判定圖G是否包含一個k頂點的完全子圖(團)，即判定是否存在V’V，|V’|=k，且對于所有的u，v∈V’，有(u，v)∈E。若用鄰接矩陣表示圖G，用二進制串表示整數k，則團問題的一個實例可以用長度為的二進位串表示。因此，團問題可表示為語言：CLIQUE={w#v|w，v∈{0，1}*，以w為鄰接矩陣的圖G有一個k頂點的團，其中v是k的二進制表示。}24算法設計與分析8.2.2P類與NP類語言接受該語言CLIQUE的非確定性算法：用非確定性選擇指令選出包含k個頂點的候選頂點子集V，然后確定性地檢查該子集是否是團問題的一個解。算法分為3個階段：算法的第一階段將輸入串w#v分解，并計算出n=，以及用v表示的整數k。若輸入不具有形式w#v或|w|不是一個平方數就拒絕該輸入。顯而易見，第一階段可在時間內完成。在算法的第二階段中，非確定性地選擇V的一個k元子集V’V。算法的第三階段是確定性地檢查V’的團性質。若V’是一個團則接受輸入，否則拒絕輸入。這顯然可以在時間內完成。因此，整個算法的時間復雜性為。非確定性算法在多項式時間內接受語言CLIQUE，故CLIQUE∈NP。

25算法設計與分析8.2.3多項式時間驗證VP={L|L∈∑*，∑為一有限字符集，存在一個多項式p和一個多項式時間驗證算法A(X，Y)使得對任意X∈∑*，X∈L當且僅當存在Y∈∑*，|Y|≤p(|X|)且A(X，Y)=1}。多項式時間可驗證語言類VP可定義為：定理8-5：VP=NP。（證明見書本）例如(哈密頓回路問題)：一個無向圖G含有哈密頓回路嗎?無向圖G的哈密頓回路是通過G的每個頂點恰好一次的簡單回路?？捎谜Z言HAM-CYCLE定義該問題如下： HAM-CYCLE={G|G含有哈密頓回路}

26算法設計與分析8.3 NP完全問題8.3.1多項式時間變換8.3.2Cook定理27算法設計與分析8.3.1多項式時間變換

定義：語言L是NP完全的當且僅當(1)L∈NP；(2)對于所有L’∈NP有L’∝pL。如果有一個語言L滿足上述性質(2)，但不一定滿足性質(1)，則稱該語言是NP難的。所有NP完全語言構成的語言類稱為NP完全語言類，記為NPC。設，是2個語言。所謂語言能在多項式時間內變換為語言(簡記為∝p)是指存在映身f:，且f滿足：(1)有一個計算f的多項式時間確定性圖靈機；(2)對于所有x∈，x∈，當且僅當f(x)∈。28算法設計與分析8.3.1多項式時間變換

定理8-6：設L是NP完全的，則(1)L∈P當且僅當P＝NP；(2)若L∝p，且∈NP，則是NP完全的。

定理8-6的(2)可用來證明問題的NP完全性。但前提是：要有第一個NP完全問題L。29算法設計與分析8.3.2Cook定理

定理8-7(Cook定理)：布爾表達式的可滿足性問題SAT是NP完全的。證明：SAT的一個實例是k個布爾變量，…，的m個布爾表達式，…，若存在各布爾變量(1≤i≤k)的0，1賦值，使每個布爾表達式(1≤i≤m)都取值1，則稱布爾表達式…是可滿足的。

SAT∈NP是很明顯的。對于任給的布爾變量，…，的0，1賦值，容易在多項式時間內驗證相應的…的取值是否為1。因此，SAT∈NP?，F(xiàn)在只要證明對任意的L∈NP有L∝pSAT即可。 （詳細證明見書本P307～310）30算法設計與分析8.4 一些典型的NP完全問題部分NP完全問題樹31算法設計與分析8.4.1合取范式的可滿足性問題

（CNF-SAT）要證明CNF-SAT∈NPC，只要證明在Cook定理中定義的布爾表達式A，…，G或者已是合取范式，或者有的雖然不是合取范式，但可以用布爾代數中的變換方法將它們化成合取范式，而且合取范式的長度與原表達式的長度只差一個常數因子。

問題描述：給定一個合取范式α，判定它是否可滿足。如果一個布爾表達式是一些因子和之積，則稱之為合取范式，簡稱CNF(ConjunctiveNormalForm)。這里的因子是變量或。例如：就是一個合取范式，而就不是合取范式。32算法設計與分析8.4.23元合取范式的可滿足性問題

（3-SAT）證明思路：

3-SAT∈NP是顯而易見的。為了證明3-SAT∈NPC，只要證明CNF-SAT∝p3-SAT，即合取范式的可滿足性問題可在多項式時間內變換為3-SAT。

問題描述：給定一個3元合取范式α，判定它是否可滿足。

33算法設計與分析8.4.3團問題CLIQUE

證明思路：

已經知道CLIQUE∈NP。通過3-SAT∝pCLIQUE來證明CLIQUE是NP難的，從而證明團問題是NP完全的。

問題描述：給定一個無向圖G=(V，E)和一個正整數k，判定圖G是否包含一個k團，即是否存在，V’V，|V’|=k，且對任意u，w∈V’有(u，w)∈E。34算法設計與分析8.4.4頂點覆蓋問題

（VERTEX-COVER）

證明思路：

首先，VERTEX-COVER∈NP。因為對于給定的圖G和正整數k以及一個“證書”V’，驗證|V’|=k，然后對每條邊(u，v)∈E，檢查是否有u∈V’或v∈V’，顯然可在多項式時間內完成。其次，通過CLIQUE∝pVERTEX-COVER來證明頂點覆蓋問題是NP難的。

問題描述：給定一個無向圖G=(V，E)和一個正整數k，判定是否存在V’V，|V’|=k，使得對于任意(u，v