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

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

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

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

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

NP完全性理論118.1.3RAM模型的變形與簡化4.位向量運算(Bit8.1.3RAM模型的變形與簡化5.判定樹判定樹是一棵二叉樹。它的每個內結點表示一個形如x∶y的比較。指向該結點左兒子的邊相應于x≤y，標號為≤。指向該結點右兒子的邊相應于x>y，標號為>。每一次比較耗費一個單位時間。下圖是對a，b，c三個數進行排序的一棵判定樹。在判定樹模型下，算法的時間復雜性可用判定樹的高度衡量。最大的比較次數是從根到葉的最長路徑的長度。NP完全性理論128.1.3RAM模型的變形與簡化5.判定樹判定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的分量。NP完全性理論138.1.3RAM模型的變形與簡化6.代數計算樹ACT 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是一個代數函數。NP完全性理論148.1.3RAM模型的變形與簡化7.代數判定樹ADT(8.1.4圖靈機1.多帶圖靈機NP完全性理論158.1.4圖靈機1.多帶圖靈機NP完全性理論158.1.4圖靈機1.多帶圖靈機

根據有限狀態控制器的當前狀態及每個讀寫頭讀到的帶符號，圖靈機的一個計算步可實現下面3個操作之一或全部。(1)改變有限狀態控制器中的狀態。(2)清除當前讀寫頭下的方格中原有帶符號并寫上新的帶符號。(3)獨立地將任何一個或所有讀寫頭，向左移動一個方格(L)或向右移動一個方格(R)或停在當前單元不動(S)。

k帶圖靈機可形式化地描述為一個7元組(Q，T，I，δ，b，q0，qf)，其中:(1)Q是有限個狀態的集合。(2)T是有限個帶符號的集合。(3)I是輸入符號的集合，IT。(4)b是惟一的空白符，b∈T-I。(5)q0是初始狀態。(6)qf是終止(或接受)狀態。(7)δ是移動函數。它是從QTk的某一子集映射到Q(T{L，R，S})k的函數。

NP完全性理論168.1.4圖靈機1.多帶圖靈機根據有限狀態控制8.1.4圖靈機1.多帶圖靈機圖靈機M的時間復雜性T(n)是它處理所有長度為n的輸入所需的最大計算步數。如果對某個長度為n的輸入，圖靈機不停機，T(n)對這個n值無定義。圖靈機的空間復雜性S(n)是它處理所有長度為n的輸入時，在k條帶上所使用過的方格數的總和。如果某個讀寫頭無限地向右移動而不停機，S(n)也無定義。與RAM模型類似，圖靈機既可作為語言接受器，也可作為計算函數的裝置。NP完全性理論178.1.4圖靈機1.多帶圖靈機圖靈機M的時間復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下的時間復雜性為。

NP完全性理論188.1.5圖靈機模型與RAM模型的關系 圖靈機模型與RA8.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的規模(大小)。當τ(n)為n的多項式時，稱問題A可在多項式時間內變換為問題B。特別地，當τ(n)為n的線性函數時，稱問題A可線性地變換為問題B。 通過問題變換的技巧，可以將2個不同問題的計算復雜性聯系在一起。這樣就可以將一個問題的計算復雜性歸結為另一個問題的計算復雜性，從而實現問題的計算復雜性歸約。NP完全性理論198.1.6問題變換與計算復雜性歸約具體地說，假設有2個問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的上界。NP完全性理論208.1.6問題變換與計算復雜性歸約 命題1(計算時間下界8.1.6問題變換與計算復雜性歸約通過問題變換獲得問題的計算時間下界的例子： (1)判別函數問題：給定n個實數，計算其判別函數。

元素惟一性問題可以在O(1)時間內變換為判別函數問題。任何一個計算判別函數的算法，計算出判別函數值后，再作一次測試，判斷其值是否為0，即可得到元素惟一性問題的解。由命題1即知，元素惟一性問題的計算時間下界也是判別函數問題的一個計算時間下界。 (2)最接近點對問題：給定平面上n個點，找出這n個點中距離最近的2個點。 在元素惟一性問題中，將每一個實數，1≤i≤n，變換為平面上的點(，0)，1≤i≤n，則元素惟一性問題可以在線性時間內變換為最接近點對問題。NP完全性理論218.1.6問題變換與計算復雜性歸約通過問題變換獲得問題的8.2P類與NP類問題8.2.1非確定性圖靈機8.2.2P類與NP類語言8.2.3多項式時間驗證NP完全性理論228.2P類與NP類問題8.2.1非確定性圖靈機NP完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)。NP完全性理論238.2.1非確定性圖靈機非確定性圖靈機（NDT8.2.2P類與NP類語言

P類和NP類語言的定義：P={L|L是一個能在多項式時間內被一臺DTM所接受的語言}NP={L|L是一個能在多項式時間內被一臺NDTM所接受的語言}由于一臺確定性圖靈機可看作是非確定性圖靈機的特例，所以可在多項式時間內被確定性圖靈機接受的語言也可在多項式時間內被非確定性圖靈機接受。故PNP。

NP完全性理論248.2.2P類與NP類語言P類和NP類語言的定義：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的每個頂點恰好一次的簡單回路。可用語言HAM-CYCLE定義該問題如下： HAM-CYCLE={G|G含有哈密頓回路}

NP完全性理論258.2.3多項式時間驗證VP={L|L∈∑*，∑從圖中的任意一點出發，路途中經過圖中每一個結點當且僅當一次，則成為哈密頓回路。要滿足兩個條件：⒈封閉的環⒉是一個連通圖，且圖中任意兩點可達經過圖（有向圖或無向圖）中所有頂點一次且僅一次的通路稱為哈密頓通路。經過圖中所有頂點一次且僅一次的回路稱為哈密頓回路。具有哈密頓回路的圖稱為哈密頓圖，具有哈密頓通路但不具有哈密頓回路的圖稱為半哈密頓圖。平凡圖是哈密頓圖。NP完全性理論26從圖中的任意一點出發，路途中經過圖中每一個結點當且僅當一次，8.3 NP完全問題8.3.1多項式時間變換8.3.2Cook定理NP完全性理論278.3 NP完全問題8.3.1多項式時間變換NP完全性理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)∈。NP完全性理論288.3.1多項式時間變換定義：語言L是NP完全的8.3.1多項式時間變換

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

(2)若L∝p，且∈NP，則是NP完全的。定理8-6的(2)可用來證明問題的NP完全性。但前提是：要有第一個NP完全問題L。NP完全性理論298.3.1多項式時間變換定理8-6：設L是NP完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。現在只要證明對任意的L∈NP有L∝pSAT即可。 （詳細證明見書本P307～310）NP完全性理論308.3.2Cook定理定理8-7(Cook定理)8.4.5子集和問題

（SUBSET-SUM）

問題描述：給定整數集合S和一個整數t，判定是否存在S的一個子集S’S，使得S’中整數的和為t。例如，若S={1，4，16，64，256，1040，1041，1093，1284，1344}且t=3754，則子集S’={1，16，64，256，1040，1093，1284}是一個解。

證明思路：

首先，對于子集和問題的一個實例<S，t>，給定一個“證書”S’，要驗證t=是否成立，顯然可在多項式時間內完成。因此，SUBSET-SUM∈NP。

NP完全性理論318.4.5子集和問題

（SUBSET-SUM）8.4.6哈密頓回路問題

（HAM-CYCLE）

證明思路：

首先，已知哈密頓回路問題是一個NP類問題。其次，通過證明3-SAT∝pHAM-CYCLE， 得出：HAM-CYCLE∈NPC。

問題描述：給定無向圖G=(V，E)，判定其是否含有一哈密頓回路。

NP完全性理論328.4.6哈密頓回路問題

（HAM-CYCLE）證明8.4.7旅行售貨員問題TSP首先，給定TSP的一個實例(G，c，k)，和一個由n個頂點組成的頂點序列。驗證算法要驗證這n個頂點組成的序列是圖G的一條回路，且經過每個頂點一次。另外，將每條邊的費用加起來，并驗證所得的和不超過k。這個過程顯然可在多項式時間內完成，即TSP∈NP。其次，旅行售貨員問題與哈密頓回路問題有著密切的聯系。哈密頓回路問題可在多項式時間內變換為旅行售貨員問題。即HAM-CYCLE∝pTSP。從而，旅行售貨員問題是NP難的。因此，TSP∈NPC。

問題描述：給定一個無向完全圖G=(V，E)及定義在VV上的一個費用函數c和一個整數k，判定G是否存在經過V中各頂點恰好一次的回路，使得該回路的費用不超過k。NP完全性理論338.4.7旅行售貨員問題TSP首先，給定TSP的第8章 NP完全性理論NP完全性理論34第8章 NP完全性理論NP完全性理論18.1 計算模型8.1.1隨機存取機RAM8.1.2隨機存取存儲程序機RASP8.1.3RAM模型的變形與簡化8.1.4圖靈機8.1.5圖靈機模型與RAM模型的關系8.1.6問題變換與計算復雜性歸約NP完全性理論358.1 計算模型8.1.1隨機存取機RAMNP完全性理論8.1.1隨機存取機RAM1.RAM的結構2.RAM程序

一個RAM程序定義了從輸入帶到輸出帶的一個映射。可以對這種映射關系作2種不同的解釋。NP完全性理論368.1.1隨機存取機RAM1.RAM的結構NP完全性理解釋一：把RAM程序看成是計算一個函數 若一個RAM程序P總是從輸入帶前n個方格中讀入n個整數x1，x2，…，xn，并且在輸出帶的第一個方格上輸出一個整數y后停機，那么就說程序P計算了函數f(x1，x2，…，xn)=yNP完全性理論37解釋一：把RAM程序看成是計算一個函數NP完全性理論4解釋二：把RAM程序當作一個語言接受器。 將字符串S=a1a2…an放在輸入帶上。在輸入帶的第一個方格中放入符號a1，第二個方格中放入符號a2，…，第n個方格中放入符號an。然后在第n+1個方格中放入0，作為輸入串的結束標志符。如果一個RAM程序P讀了字符串S及結束標志符0后，在輸出帶的第一格輸出一個1并停機，就說程序P接受字符串S。NP完全性理論38解釋二：把RAM程序當作一個語言接受器。NP完全性理論58.1.1隨機存取機RAM3.RAM程序的耗費標準標準一：均勻耗費標準 在均勻耗費標準下，每條RAM指令需要一個單位時間；每個寄存器占用一個單位空間。以后除特別注明，RAM程序的復雜性將按照均勻耗費標準衡量。標準二：對數耗費標準 對數耗費標準是基于這樣的假定，即執行一條指令的耗費與以二進制表示的指令的操作數長度成比例。在RAM計算模型下，假定一個寄存器可存放一個任意大小的整數。因此若設l(i)是整數i所占的二進制位數，則NP完全性理論398.1.1隨機存取機RAM3.RAM程序的耗費標準標準8.1.2隨機存取存儲程序機RASP1.RASP的結構 RASP的整體結構類似于RAM，所不同的是RASP的程序是存儲在寄存器中的。每條RASP指令占據2個連續的寄存器。第一個寄存器存放操作碼的編碼，第二個寄存器存放地址。RASP指令用整數進行編碼。2.RASP程序的復雜性 不管是在均勻耗費標準下，還是在對數耗費標準下，RAM程序和RASP程序的復雜性只差一個常數因子。在一個計算模型下T(n)時間內完成的輸入-輸出映射可在另一個計算模型下模擬，并在kT(n)時間內完成。其中k是一個常數因子。空間復雜性的情況也是類似的。NP完全性理論408.1.2隨機存取存儲程序機RASP1.RASP的結構8.1.3RAM模型的變形與簡化1.實隨機存取機

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

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

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

NP完全性理論448.1.3RAM模型的變形與簡化4.位向量運算(Bit8.1.3RAM模型的變形與簡化5.判定樹判定樹是一棵二叉樹。它的每個內結點表示一個形如x∶y的比較。指向該結點左兒子的邊相應于x≤y，標號為≤。指向該結點右兒子的邊相應于x>y，標號為>。每一次比較耗費一個單位時間。下圖是對a，b，c三個數進行排序的一棵判定樹。在判定樹模型下，算法的時間復雜性可用判定樹的高度衡量。最大的比較次數是從根到葉的最長路徑的長度。NP完全性理論458.1.3RAM模型的變形與簡化5.判定樹判定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的分量。NP完全性理論468.1.3RAM模型的變形與簡化6.代數計算樹ACT 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是一個代數函數。NP完全性理論478.1.3RAM模型的變形與簡化7.代數判定樹ADT(8.1.4圖靈機1.多帶圖靈機NP完全性理論488.1.4圖靈機1.多帶圖靈機NP完全性理論158.1.4圖靈機1.多帶圖靈機

根據有限狀態控制器的當前狀態及每個讀寫頭讀到的帶符號，圖靈機的一個計算步可實現下面3個操作之一或全部。(1)改變有限狀態控制器中的狀態。(2)清除當前讀寫頭下的方格中原有帶符號并寫上新的帶符號。(3)獨立地將任何一個或所有讀寫頭，向左移動一個方格(L)或向右移動一個方格(R)或停在當前單元不動(S)。

k帶圖靈機可形式化地描述為一個7元組(Q，T，I，δ，b，q0，qf)，其中:(1)Q是有限個狀態的集合。(2)T是有限個帶符號的集合。(3)I是輸入符號的集合，IT。(4)b是惟一的空白符，b∈T-I。(5)q0是初始狀態。(6)qf是終止(或接受)狀態。(7)δ是移動函數。它是從QTk的某一子集映射到Q(T{L，R，S})k的函數。

NP完全性理論498.1.4圖靈機1.多帶圖靈機根據有限狀態控制8.1.4圖靈機1.多帶圖靈機圖靈機M的時間復雜性T(n)是它處理所有長度為n的輸入所需的最大計算步數。如果對某個長度為n的輸入，圖靈機不停機，T(n)對這個n值無定義。圖靈機的空間復雜性S(n)是它處理所有長度為n的輸入時，在k條帶上所使用過的方格數的總和。如果某個讀寫頭無限地向右移動而不停機，S(n)也無定義。與RAM模型類似，圖靈機既可作為語言接受器，也可作為計算函數的裝置。NP完全性理論508.1.4圖靈機1.多帶圖靈機圖靈機M的時間復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下的時間復雜性為。

NP完全性理論518.1.5圖靈機模型與RAM模型的關系 圖靈機模型與RA8.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的規模(大小)。當τ(n)為n的多項式時，稱問題A可在多項式時間內變換為問題B。特別地，當τ(n)為n的線性函數時，稱問題A可線性地變換為問題B。 通過問題變換的技巧，可以將2個不同問題的計算復雜性聯系在一起。這樣就可以將一個問題的計算復雜性歸結為另一個問題的計算復雜性，從而實現問題的計算復雜性歸約。NP完全性理論528.1.6問題變換與計算復雜性歸約具體地說，假設有2個問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的上界。NP完全性理論538.1.6問題變換與計算復雜性歸約 命題1(計算時間下界8.1.6問題變換與計算復雜性歸約通過問題變換獲得問題的計算時間下界的例子： (1)判別函數問題：給定n個實數，計算其判別函數。

元素惟一性問題可以在O(1)時間內變換為判別函數問題。任何一個計算判別函數的算法，計算出判別函數值后，再作一次測試，判斷其值是否為0，即可得到元素惟一性問題的解。由命題1即知，元素惟一性問題的計算時間下界也是判別函數問題的一個計算時間下界。 (2)最接近點對問題：給定平面上n個點，找出這n個點中距離最近的2個點。 在元素惟一性問題中，將每一個實數，1≤i≤n，變換為平面上的點(，0)，1≤i≤n，則元素惟一性問題可以在線性時間內變換為最接近點對問題。NP完全性理論548.1.6問題變換與計算復雜性歸約通過問題變換獲得問題的8.2P類與NP類問題8.2.1非確定性圖靈機8.2.2P類與NP類語言8.2.3多項式時間驗證NP完全性理論558.2P類與NP類問題8.2.1非確定性圖靈機NP完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)。NP完全性理論568.2.1非確定性圖靈機非確定性圖靈機（NDT8.2.2P類與NP類語言

P類和NP類語言的定義：P={L|L是一個能在多項式時間內被一臺DTM所接受的語言}NP={L|L是一個能在多項式時間內被一臺NDTM所接受的語言}由于一臺確定性圖靈機可看作是非確定性圖靈機的特例，所以可在多項式時間內被確定性圖靈機接受的語言也可在多項式時間內被非確定性圖靈機接受。故PNP。

NP完全性理論578.2.2P類與NP類語言P類和NP類語言的定義：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的每個頂點恰好一次的簡單回路。可用語言HAM-CYCLE定義該問題如下： HAM-CYCLE={G|G含有哈密頓回路}

NP完全性理論588.2.3多項式時間驗證VP={L|L∈∑*，∑從圖中的任意一點出發，路途中經過圖中每一個結點當且僅當一次，則成為哈密頓回路。要滿足兩個條件：⒈封閉的環⒉是一個連通圖，且圖中任意兩點可達經過圖（有向圖或無向圖）中所有頂點一次且僅一次的通路稱為哈密頓通路。經過圖中所有頂點一次且僅一次的回路稱為哈密頓回路。具有哈密頓回路的圖稱為哈密頓圖，具有哈密頓通路但不具有哈密頓回路的圖稱為半哈密頓圖。平凡圖是哈密頓圖。NP完全性理論59從圖中的任意一點出發，路途中經過圖中每一個結點當且僅當一次，8.3 NP完全問題8.3.1多項式時間變換8.3.2Cook定理NP完全性理論608.3 NP完全問題8.3.1多項式時間變換NP完全性理8.3.1多項式時間變換

定義：語言L是NP完全的當且僅當(1)L∈NP；(2)對于所有L’∈NP有L’∝pL。如果有一個語言L滿足