NP完全性理論課件

第8章 NP完全性理論NP完全性理論18.1 計算模型8.1.1隨機存取機RAM8.1.2隨機存取存儲程序機RASP8.1.3RAM模型的變形與簡化8.1.4圖靈機8.1.5圖靈機模型與RAM模型的關(guān)系8.1.6問題變換與計算復(fù)雜性歸約NP完全性理論28.1.1隨機存取機RAM1.RAM的結(jié)構(gòu)2.RAM程序

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

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

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

代表異或，

代表非。在位式計算模型下，每個邏輯運算指令耗費一個單位時間。

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

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

op或op或其中，和分別是結(jié)點v在樹T中的祖先結(jié)點v1和v2處得到的結(jié)果值，或是x的分量；op∈{+，－，×，/}；c是一個常數(shù)。(3)每個有2個兒子的內(nèi)部結(jié)點(分支結(jié)點)v，表示下列形式的測試指令：>0或≥0或=0其中，是結(jié)點v在樹T中的祖先結(jié)點v1處得到的結(jié)果值，或是x的分量。NP完全性理論138.1.3RAM模型的變形與簡化7.代數(shù)判定樹ADT(AlgebraicDecisionTree) 在代數(shù)計算樹T中，若將所有的簡單結(jié)點都壓縮到其最近的子孫分支結(jié)點處，并將簡單結(jié)點處的計算在壓縮后的分支結(jié)點處同時完成，則計算結(jié)果可看作是輸入x的一個代數(shù)函數(shù)fv(x)。由此引出另一個稱為代數(shù)判定樹的計算模型。代數(shù)判定樹T是一棵二叉樹，且(1)每個葉結(jié)點表示輸出結(jié)果YES或NO。(2)每個內(nèi)部結(jié)點v表示一個形如fv(x1，x2，…，xn)∶0的比較。其中，x=(x1，x2，…，xn)是輸入，fv是一個代數(shù)函數(shù)。NP完全性理論148.1.4圖靈機1.多帶圖靈機NP完全性理論158.1.4圖靈機1.多帶圖靈機

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

k帶圖靈機可形式化地描述為一個7元組(Q，T，I，δ，b，q0，qf)，其中:(1)Q是有限個狀態(tài)的集合。(2)T是有限個帶符號的集合。(3)I是輸入符號的集合，I

T。(4)b是惟一的空白符，b∈T-I。(5)q0是初始狀態(tài)。(6)qf是終止(或接受)狀態(tài)。(7)δ是移動函數(shù)。它是從Q

Tk的某一子集映射到Q

(T

{L，R，S})k的函數(shù)。

NP完全性理論168.1.4圖靈機1.多帶圖靈機圖靈機M的時間復(fù)雜性T(n)是它處理所有長度為n的輸入所需的最大計算步數(shù)。如果對某個長度為n的輸入，圖靈機不停機，T(n)對這個n值無定義。圖靈機的空間復(fù)雜性S(n)是它處理所有長度為n的輸入時，在k條帶上所使用過的方格數(shù)的總和。如果某個讀寫頭無限地向右移動而不停機，S(n)也無定義。與RAM模型類似，圖靈機既可作為語言接受器，也可作為計算函數(shù)的裝置。NP完全性理論178.1.5圖靈機模型與RAM模型的關(guān)系 圖靈機模型與RAM模型的關(guān)系是指同一問題在這2種不同計算模型下的復(fù)雜性之間的關(guān)系。

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

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

命題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的一個計算時間上界。 問題的變換與問題的計算復(fù)雜性歸約的關(guān)系： 在命題1和命題2中，當(dāng)τ(n)=o(T(n))時，問題A的下界歸約為問題B的下界，問題B的上界歸約為問題A的上界。NP完全性理論208.1.6問題變換與計算復(fù)雜性歸約通過問題變換獲得問題的計算時間下界的例子： (1)判別函數(shù)問題：給定n個實數(shù)，計算其判別函數(shù)。

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

非確定性圖靈機（NDTM）：一個k帶的非確定性圖靈機M是一個7元組：(Q，T，I，δ，b，q0，qf)。與確定性圖靈機不同的是非確定性圖靈機允許移動函數(shù)δ具有不確定性，即對于Q

Tk中的每一個值(q;x1,x2,…,xk)，當(dāng)它屬于δ的定義域時，Q

(T

{L，R，S})k中有惟一的一個子集δ(q;x1,x2,…,xk)與之對應(yīng)?？梢栽讦?q;x1,x2,…,xk)中隨意選定一個值作為它的函數(shù)值。在圖靈機計算模型中，移動函數(shù)δ是單值的，即對于Q

Tk中的每一個值，當(dāng)它屬于δ的定義域時，Q

(T

{L，R，S})k中只有惟一的值與之對應(yīng)，稱這種圖靈機為確定性圖靈機，簡記為DTM(DeterministicTuringMachine)。NP完全性理論238.2.2P類與NP類語言

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

NP。

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

NP完全性理論25從圖中的任意一點出發(fā)，路途中經(jīng)過圖中每一個結(jié)點當(dāng)且僅當(dāng)一次，則成為哈密頓回路。要滿足兩個條件：⒈封閉的環(huán)⒉是一個連通圖，且圖中任意兩點可達(dá)經(jīng)過圖（有向圖或無向圖）中所有頂點一次且僅一次的通路稱為哈密頓通路。經(jīng)過圖中所有頂點一次且僅一次的回路稱為哈密頓回路。具有哈密頓回路的圖稱為哈密頓圖，具有哈密頓通路但不具有哈密頓回路的圖稱為半哈密頓圖。平凡圖是哈密頓圖。NP完全性理論268.3 NP完全問題8.3.1多項式時間變換8.3.2Cook定理NP完全性理論278.3.1多項式時間變換

定義：語言L是NP完全的當(dāng)且僅當(dāng)(1)L∈NP；(2)對于所有L’∈NP有L’∝pL。如果有一個語言L滿足上述性質(zhì)(2)，但不一定滿足性質(zhì)(1)，則稱該語言是NP難的。所有NP完全語言構(gòu)成的語言類稱為NP完全語言類，記為NPC。

設(shè)，是2個語言。所謂語言能在多項式時間內(nèi)變換為語言(簡記為∝p)是指存在映設(shè)f:，且f滿足：(1)有一個計算f的多項式時間確定性圖靈機；(2)對于所有x∈，x∈，當(dāng)且僅當(dāng)f(x)∈。NP完全性理論288.3.1多項式時間變換

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

(2)若L∝p，且∈NP，則是NP完全的。定理8-6的(2)可用來證明問題的NP完全性。但前提是：要有第一個NP完全問題L。NP完全性理論298.3.2Cook定理

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

SAT∈NP是很明顯的。對于任給的布爾變量，…，的0，1賦值，容易在多項式時間內(nèi)驗證相應(yīng)的…的取值是否為1。因此，SAT∈NP?，F(xiàn)在只要證明對任意的L∈NP有L∝pSAT即可。 （詳細(xì)證明見書本P307～310）NP完全性理論308.4.5子集和問題

（SUBSET-SUM）

問題描述：給定整數(shù)集合S和一個整數(shù)t，判定是否存在S的一個子集S’

S，使得S’中