計(jì)算機(jī)算法基礎(chǔ) 第2版 課件 第14章 NP-完全問(wèn)題

1第14

章

NP-完全問(wèn)題序言

2預(yù)備知識(shí)

4P和NP語(yǔ)言類(lèi)

20NPC語(yǔ)言類(lèi)和NPC問(wèn)題

29第一個(gè)NPC問(wèn)題

32若干著名NPC問(wèn)題的證明

431.序言2有些看似容易的問(wèn)題找不到多項(xiàng)式算法。例如，在圖中找一條兩點(diǎn)間最長(zhǎng)的簡(jiǎn)單路徑。不論k多大，都找不到O(nk)的算法。這引起人們對(duì)問(wèn)題本身固有的難易程度的探討興趣，也是這一章討論的課題。問(wèn)題分類(lèi)。有多項(xiàng)式算法的問(wèn)題稱(chēng)為可駕馭的(tractable)問(wèn)題，或稱(chēng)為容易問(wèn)題，否則稱(chēng)為不可駕馭的(intractable)問(wèn)題，或難問(wèn)題。NP完全問(wèn)題(NP-complete問(wèn)題，簡(jiǎn)稱(chēng)NPC問(wèn)題)簡(jiǎn)單說(shuō)，是至今還無(wú)法判斷屬于容易問(wèn)題，還是難問(wèn)題的一類(lèi)問(wèn)題。為了理解NPC問(wèn)題，我們將先介紹P類(lèi)和NP類(lèi)問(wèn)題。3P類(lèi)問(wèn)題有多項(xiàng)式算法的問(wèn)題屬于P類(lèi)。也可認(rèn)為，在一個(gè)確定的圖靈機(jī)上有多項(xiàng)式算法。(后面會(huì)定義圖靈機(jī))NP類(lèi)問(wèn)題在非確定的圖靈機(jī)上有多項(xiàng)式算法的問(wèn)題屬于NP類(lèi)。許多難以判斷的問(wèn)題都屬于這一類(lèi)，例如哈密爾頓回路問(wèn)題、最小頂點(diǎn)復(fù)蓋問(wèn)題、圖的三著色問(wèn)題等。NPC類(lèi)問(wèn)題NPC類(lèi)是NP類(lèi)中最困難的問(wèn)題，NPC

NP。如果NPC中有一個(gè)有多項(xiàng)式算法，那么所有NP問(wèn)題都有多項(xiàng)式算法。反之，如有一個(gè)沒(méi)有多項(xiàng)式算法，那么所有NPC問(wèn)題都沒(méi)有多項(xiàng)式算法。P

NP猜想已證明PNP，猜想PNPC=，即P

NP，但至今未能證明。4圖靈機(jī)圖靈機(jī)TM，通常指確定的圖靈機(jī)(DeterministicTuringMachine)，是一個(gè)簡(jiǎn)單的計(jì)算模型。10B101BB

有限狀態(tài)控制器(q,a)(q’,a’,D)2.預(yù)備知識(shí)由一個(gè)有限狀態(tài)控制器和一條右端無(wú)限長(zhǎng)的讀寫(xiě)帶組成。讀寫(xiě)帶從左到右劃分為無(wú)限多個(gè)連續(xù)的方格，每個(gè)方格可存放字符集

中的一個(gè)符號(hào)。空白的格子由特殊符號(hào)B表示。Q是個(gè)有限個(gè)狀態(tài)的集合。有限狀態(tài)控制器在任一時(shí)刻處于Q中的一個(gè)狀態(tài)q并控制讀寫(xiě)頭的讀寫(xiě)操作。一開(kāi)始在初始狀態(tài)q0。(接下頁(yè))5如果有限狀態(tài)控制器當(dāng)前的狀態(tài)是q

Q，其讀寫(xiě)頭正在掃描的字符是a

，那么，有限狀態(tài)控制器做三件事：更改下一時(shí)刻的狀態(tài)為q’

更新所掃描的字符為a’決定讀寫(xiě)頭向左(L)移動(dòng)一個(gè)方格，或向右(R)移動(dòng)一個(gè)方格，或停留不動(dòng)(N)。上述三件事都是確定好的，可以表示為(q,a)

(q’,a’,D)，或者

(q,a)=(q’,a’,D)，這里D可以是L，R，或者N。

稱(chēng)為狀態(tài)轉(zhuǎn)換函數(shù)，允許q’=q

和a’=a。因?yàn)榧螿和

都是有限集合，

(q,a)轉(zhuǎn)換函數(shù)可以用一個(gè)有限長(zhǎng)的表格表示。集合Q有子集F

Q，子集F

中的狀態(tài)稱(chēng)為終止?fàn)顟B(tài)。第13章的有限狀態(tài)自動(dòng)機(jī)是圖靈機(jī)的特殊情況。它不改變讀寫(xiě)帶上的字符，沒(méi)有輸出值，停機(jī)在接收狀態(tài)表示接收輸入字符串。6圖靈機(jī)計(jì)算一個(gè)函數(shù)或識(shí)別一個(gè)字符串的過(guò)程開(kāi)始時(shí)，輸入數(shù)據(jù)或字符串從左邊第一個(gè)方格開(kāi)始放在讀寫(xiě)帶上，圖靈機(jī)處在開(kāi)始狀態(tài)q0，而讀寫(xiě)頭指向第一個(gè)方格。·然后，根據(jù)轉(zhuǎn)換函數(shù)不斷地變更狀態(tài)、修改符號(hào)、和移動(dòng)讀寫(xiě)頭。當(dāng)進(jìn)入了一個(gè)終止?fàn)顟B(tài)qf

F時(shí)，計(jì)算停止。這時(shí)，在帶子上的字符串或在某些指定格子上符號(hào)就是輸出的函數(shù)值。如果用來(lái)識(shí)別一個(gè)字符串，可以輸出一個(gè)特定符號(hào)(比如1)表示接收這個(gè)字符串，輸出另一特定符號(hào)(比如0)表示拒絕這個(gè)字符串。圖靈機(jī)有可能永遠(yuǎn)不能進(jìn)入終止?fàn)顟B(tài)，這時(shí)我們說(shuō)函數(shù)對(duì)輸入數(shù)據(jù)無(wú)定義或者說(shuō)圖靈機(jī)對(duì)輸入字符串不能判定。圖靈機(jī)的計(jì)算復(fù)雜度定義為其狀態(tài)轉(zhuǎn)換的次數(shù)T(n)，這里n是輸入字符串的長(zhǎng)度，并且只對(duì)停機(jī)的情況才考慮復(fù)雜度。7符號(hào)集和編碼對(duì)計(jì)算復(fù)雜度的影響用不同的符號(hào)集合會(huì)影響輸入規(guī)模的大小。比如整數(shù)98，用十進(jìn)制，只要兩個(gè)符號(hào)9和8表示；如果用2進(jìn)制，98=11000102則需要7個(gè)符號(hào)表示；如果用1進(jìn)制，則需要98個(gè)0表示。設(shè)某圖靈機(jī)T使用的符號(hào)集是

，|

|=d，d

2?，F(xiàn)在假設(shè)有另一個(gè)圖靈機(jī)T’，它做一次狀態(tài)轉(zhuǎn)換所需時(shí)間與T相同，但字符集

’與

不同，|’

|

2。我們可用

’中兩字符a和b(可視為0和1)來(lái)對(duì)

中每個(gè)字符編碼，長(zhǎng)為k=

lgd

。這樣一來(lái)，對(duì)

中一個(gè)字符的操作變成了對(duì)一個(gè)長(zhǎng)為k的序列的操作。因?yàn)閐和k都是常數(shù)，圖靈機(jī)T’的漸近復(fù)雜度與T的相同。所以，除一進(jìn)制的編碼外，用不同的符號(hào)集不影響算法的復(fù)雜度。為方便起見(jiàn)，以下討論中，我們就假定

={0,1}。8判斷型問(wèn)題和優(yōu)化型問(wèn)題及其關(guān)系如果一個(gè)問(wèn)題的答案只有兩種，是(yes)或不是(no)，則稱(chēng)為一個(gè)判斷型問(wèn)題。例如，判斷一個(gè)圖是否有一條哈密爾頓回路就是一個(gè)判斷型問(wèn)題。一個(gè)問(wèn)題被稱(chēng)為優(yōu)化型問(wèn)題，如果這個(gè)問(wèn)題的解對(duì)應(yīng)于一個(gè)最佳的數(shù)值，例如在圖中找一個(gè)最短路徑。不同的優(yōu)化型問(wèn)題有著不同的優(yōu)化目標(biāo)和量綱。例如，要求解必須是最長(zhǎng)、最短、最大、最小、最高、最低、最重、或最輕等等。不便于討論不同問(wèn)題之間的關(guān)系。討論NP完全問(wèn)題時(shí)，我們限定所有被分類(lèi)的問(wèn)題都是判斷型問(wèn)題。這一簡(jiǎn)化使我們可以討論任何兩個(gè)判斷型問(wèn)題之間的關(guān)系。只要兩個(gè)問(wèn)題的解都是yes，則可認(rèn)為它們有同解。這對(duì)NP完全問(wèn)題的研究起著奠基性的關(guān)鍵作用。(接下頁(yè))9判斷型問(wèn)題和優(yōu)化型問(wèn)題及其關(guān)系(繼續(xù))只限于判斷型問(wèn)題的討論不會(huì)影響NPC理論的應(yīng)用價(jià)值，因?yàn)橐粋€(gè)優(yōu)化型問(wèn)題往往可對(duì)應(yīng)于一個(gè)判斷型問(wèn)題。而且，如果對(duì)應(yīng)的判斷型問(wèn)題有多項(xiàng)式算法，那么其對(duì)應(yīng)的優(yōu)化型問(wèn)題也往往有多項(xiàng)式算法。下面看一個(gè)例子。例14.1一個(gè)優(yōu)化型問(wèn)題定義如下：給定一個(gè)連通的無(wú)向圖G(V,E)以及V中兩頂點(diǎn)s和t，找出一條從s到t的簡(jiǎn)單路徑使得它含有的邊最多。為上述優(yōu)化問(wèn)題定義一個(gè)對(duì)應(yīng)的判斷型問(wèn)題；假設(shè)(a)中的判斷型問(wèn)題有多項(xiàng)式算法A，以算法A為子程序，設(shè)計(jì)一個(gè)多項(xiàng)式算法來(lái)解決對(duì)應(yīng)的優(yōu)化問(wèn)題。解：(a) 我們引入一個(gè)變量k后，這個(gè)判斷型問(wèn)題可定義如下：給定連通的無(wú)向圖G(V,E)和正整數(shù)k，以及V中兩頂點(diǎn)s和t，是否存在一條含至少k條邊的從s到t的簡(jiǎn)單路徑？(接下頁(yè))10例14.1解(繼續(xù))(b) 優(yōu)化型問(wèn)題的算法如下。第一步確定最長(zhǎng)路徑的邊的個(gè)數(shù)k。第二步測(cè)試每條邊。如果刪去這條邊后，圖中仍有長(zhǎng)為k的路徑，則刪去，否則保留。每條邊都測(cè)試后，剩下的邊必定形成一條長(zhǎng)為k的路徑。設(shè)(a)的多項(xiàng)式算法為A(G,s,t,k)，算法偽碼如下：Longest-path(G(V,E),s,t)k

n-1whileA(G,s,t,k)=no；

k

k-1；endwhile；

//最長(zhǎng)路徑有k條邊G’(V’,E’)

G(V,E) //復(fù)制一個(gè)G(V,E)，V’=V，E’=Eforeache

E’ E’

E’–{e} //從E’中刪去e ifA(G’,s,t,k)=no //如果G’中不再存在長(zhǎng)為k的路徑

thenE’

E’

{e} //把e放回來(lái) endifendforreturn

G’End11判斷型問(wèn)題的形式語(yǔ)言表示給定字符集

，它的所有字符串的集合，包括空串

，稱(chēng)為

的全語(yǔ)言，記為

*。例如，

={0,1}，

*={

,0,1,00,01,10,…}。給定字符集

，它的全語(yǔ)言的一個(gè)子集L

*稱(chēng)為定義在

上的一個(gè)語(yǔ)言。換句話說(shuō)，任何一個(gè)

上的字符串的集合稱(chēng)為一個(gè)語(yǔ)言。我們只對(duì)有意義的語(yǔ)言感興趣，例如，L={10,11,111,1011,…}代表所有質(zhì)數(shù)的集合。一個(gè)“問(wèn)題”

是一個(gè)抽象的定義，它由許許多多的實(shí)例所組成。比如，“哈密爾頓回路問(wèn)題”包含了所有圖的哈密爾頓回路問(wèn)題。對(duì)一個(gè)具體的圖來(lái)講，比如圖8-1(a)，它是否有哈密爾頓回路的問(wèn)題，是“哈密爾頓回路問(wèn)題”的一個(gè)實(shí)例。一個(gè)實(shí)例，也必須是一個(gè)實(shí)例才可以用一個(gè)0和1的字符串x表示。(接下頁(yè))12判斷型問(wèn)題的形式語(yǔ)言表示

(繼續(xù))反之，給定一個(gè)子符串x，可以有三種情況：x代表問(wèn)題

的一個(gè)實(shí)例并且有答案yes；x代表問(wèn)題

的一個(gè)實(shí)例并且有答案no；x不代表問(wèn)題

的一個(gè)實(shí)例，而是一個(gè)雜亂的子符串。用

(x)=1表示

第1種情況，用

(x)=0表示

第2,3種情況。給定一個(gè)判斷型問(wèn)題

，它對(duì)應(yīng)的語(yǔ)言L(

)是有yes答案的所有實(shí)例的子符串的編碼的集合：

L(

)={x|x

*and

(x)=1}。例如，哈密爾頓回路問(wèn)題對(duì)應(yīng)的語(yǔ)言可表示為： Hamilton-Cycle={<G>|G含有哈密爾頓回路}。這里，Hamilton-Cycle是這個(gè)語(yǔ)言的名字，而<G>是對(duì)一個(gè)實(shí)例，圖G，的編碼的字符串。13判斷型問(wèn)題的算法解一個(gè)判斷型問(wèn)題

的算法A所做的事就是對(duì)任何一個(gè)輸入字符串x

*進(jìn)行掃描和運(yùn)算，然后輸出答案A(x)。答案的形式有：A(x)=1

表示接收x，A(x)=0

表示拒絕x，和不回答，

表示不能判定x。所以，解一個(gè)判斷型問(wèn)題

的算法就等價(jià)于一個(gè)識(shí)別語(yǔ)言L(

)的算法。也就是識(shí)別任一給定字符串x是否有x

L(

)。我們把這樣的算法稱(chēng)為判斷型算法。為簡(jiǎn)便起見(jiàn)，除非特別說(shuō)明，本章討論的問(wèn)題和算法都是指判斷型問(wèn)題和算法。14定義14.4

給定一個(gè)算法A，所有被A所接收的子符串的集合，L={x|A(x)=1}，稱(chēng)為被A所接收(Accepted)的語(yǔ)言。進(jìn)一步，如果A對(duì)其他的子符串都拒絕，即

y

L，A(y)=0，則稱(chēng)語(yǔ)言L被A所判定(Decided)。定義14.5

給定一個(gè)問(wèn)題

，如果它對(duì)應(yīng)的語(yǔ)言L(

)正好等于被算法A所接收的語(yǔ)言，那么稱(chēng)問(wèn)題

或語(yǔ)言L(

)被A所接收。如果問(wèn)題

對(duì)應(yīng)的語(yǔ)言L(

)正好等于被算法A所判定的語(yǔ)言，那么稱(chēng)問(wèn)題

或語(yǔ)言L(

)被A所判定。顯然，給定問(wèn)題

，如果能找到算法A使L(

)被A所判定，那么我們就解決了這個(gè)問(wèn)題。但是，重要的問(wèn)題是算法A的復(fù)雜度。給定一個(gè)問(wèn)題

，我們總是希望找到一個(gè)復(fù)雜度小的算法來(lái)判定，至少是有多項(xiàng)式的復(fù)雜度，但往往不容易。下面討論復(fù)雜度問(wèn)題。15多項(xiàng)式關(guān)聯(lián)兩個(gè)計(jì)算模型T1和T2稱(chēng)為多項(xiàng)式關(guān)聯(lián)的，如果對(duì)任一個(gè)判斷型問(wèn)題，T1上存在一個(gè)多項(xiàng)式復(fù)雜度的判定算法，當(dāng)且僅當(dāng)

T2上存在一個(gè)多項(xiàng)式復(fù)雜度的判定算法。顯然，如果計(jì)算模型T1和T2是多項(xiàng)式關(guān)聯(lián)的話，那么在我們討論一個(gè)問(wèn)題是否有多項(xiàng)式算法時(shí)，用哪一個(gè)計(jì)算模型都不影響這個(gè)問(wèn)題的結(jié)論。因?yàn)閳D靈機(jī)和其他現(xiàn)代計(jì)算機(jī)的抽象模型被證明都是多項(xiàng)式關(guān)聯(lián)的，所以我們可隨意用其中的一個(gè)模型來(lái)討論。下面，如不加說(shuō)明，我們用的是圖靈機(jī)的模型。16多項(xiàng)式歸約定義14.6

給定兩個(gè)語(yǔ)言L1和L2，如果存在一個(gè)算法f，它把

*中每一個(gè)字符串x轉(zhuǎn)換為另一個(gè)字符串f(x)，并且滿足：x

L1

當(dāng)且僅當(dāng)f(x)

L2；f是個(gè)多項(xiàng)式算法，即轉(zhuǎn)換在O(|x|c)的時(shí)間內(nèi)完成，這里c是一個(gè)正數(shù)常數(shù)；那么，我們說(shuō)L1可多項(xiàng)式歸約到L2，記為L(zhǎng)1

p

L2，并稱(chēng)f為多項(xiàng)式轉(zhuǎn)換函數(shù)或算法。多項(xiàng)式歸約中轉(zhuǎn)換函數(shù)f把

*中每一個(gè)字符串映射到另一個(gè)字符串。這個(gè)映射不要求單射(onetoone)，也不要求滿射(onto)，但一定要把L1

內(nèi)的一個(gè)字符串映射到L2

內(nèi)的一個(gè)字符，把L1

外的一個(gè)字符串映射到L2

外的一個(gè)字符串。下圖(14-2)解釋了這個(gè)映射關(guān)系。17圖14-2定義14.7 假設(shè)問(wèn)題

1和

2對(duì)應(yīng)的語(yǔ)言是L(

1)和L(

2)。如果語(yǔ)言L(

1)可多項(xiàng)式歸約到語(yǔ)言L(

2)，則稱(chēng)問(wèn)題

1可多項(xiàng)式歸約到問(wèn)題

2，記為

1

p

2。從問(wèn)題的角度看，

1

p

2意味著

1的任何實(shí)例x被一多項(xiàng)式轉(zhuǎn)換算法f變?yōu)?/p>

2的一個(gè)實(shí)例f(x)并且

1(x)=yes

當(dāng)且僅當(dāng)

2(f(x))=yes。18定理14.1

如果L1

p

L2，而語(yǔ)言L2可被一多項(xiàng)式算法A2所判定，那么必存在一個(gè)多項(xiàng)式算法A1使語(yǔ)言L1被A1所判定。證明：

如下圖(14-3)所示，我們可這樣設(shè)計(jì)A1:對(duì)任一個(gè)字符串x，A1先用多項(xiàng)式轉(zhuǎn)換函數(shù)f把x轉(zhuǎn)換為f(x)，然后讓算法A2去判定。如果A2(f(x))=1，則輸出A1(x)=1，否則有A2(f(x))=0，則輸出A1(x)=0。由于f(x)

L2

當(dāng)且僅當(dāng)x

L1，所以算法A1可正確地判定語(yǔ)言L1。(接下頁(yè))算法fxf(x)A2yes,f(x)

L2yes,x

L1no,x

L1no,f(x)

L2A1圖14-319注評(píng)：如果問(wèn)題

1可多項(xiàng)式歸約到問(wèn)題

2，那么從多項(xiàng)式可解的角度看，問(wèn)題

2可認(rèn)為比

1更難，因?yàn)檎业?/p>

2的多項(xiàng)式算法就可以有

1的多項(xiàng)式算法。如果問(wèn)題

2也可以多項(xiàng)式歸約到問(wèn)題

1，那么我們認(rèn)為兩者在多項(xiàng)式可解上等價(jià)。證明

(繼續(xù))算法A1所用的時(shí)間是由兩部分組成，第一部分是把x轉(zhuǎn)換為f(x)的時(shí)間t1，第二部分是算法A2判定f(x)的時(shí)間t2。設(shè)|x|=n，因f是多項(xiàng)式轉(zhuǎn)換函數(shù)，不妨設(shè)

t1

<nc，這里c是一個(gè)大于0的常數(shù)，并且有|f(x)|

nc，這是因?yàn)樵趎c步時(shí)間內(nèi)，算法不可能產(chǎn)生多于nc個(gè)字符。

又因?yàn)樗惴ˋ2是個(gè)多項(xiàng)式算法，所以t2<|f(x)|k

≤

nck，這里k也是一個(gè)正的常數(shù)。因此t1+t2=O(nc+nck)，算法A1是個(gè)多項(xiàng)式算法。

20上一節(jié)把問(wèn)題

對(duì)應(yīng)于

={0,1}上的一個(gè)語(yǔ)言L(

)。因此，對(duì)問(wèn)題的分類(lèi)也就是對(duì)語(yǔ)言的分類(lèi)。P語(yǔ)言類(lèi)定義14.8

P語(yǔ)言類(lèi)(classP)是可以在多項(xiàng)式時(shí)間內(nèi)被算法判定的語(yǔ)言的集合，即P={L|L

*可被一多項(xiàng)式算法所判定}。如果

對(duì)應(yīng)的語(yǔ)言L(

)屬于P類(lèi)，那么問(wèn)題

也稱(chēng)為P類(lèi)問(wèn)題。定理14.2

如果語(yǔ)言L可以被一個(gè)算法在多項(xiàng)式時(shí)間內(nèi)接收，那么L就可以被一個(gè)算法在多項(xiàng)式時(shí)間內(nèi)判定。證明：如果L可被算法A在多項(xiàng)式時(shí)間內(nèi)接收，那么存在c>0，使得對(duì)任一字符串x

L，算法A在|x|c步內(nèi)輸出A(x)=1。所以，如果x

L，那么算法A會(huì)在|x|c步內(nèi)輸出A(x)=0或者不做判定。(接下頁(yè))3.P和NP語(yǔ)言類(lèi)

21證明(繼續(xù))：如果算法A在|x|c步內(nèi)不做判定，則表明x必定不屬于L。所以，既使算法A在|x|c步內(nèi)不做判定，x

L的結(jié)論已可做出。所以，我們可以設(shè)計(jì)算法B，對(duì)任一輸入字符串x，它在|x|c步內(nèi)和算法A的動(dòng)作完全一樣，而在|x|c步之后，如果A還沒(méi)有做出判定，則輸出B(x)=0。顯然語(yǔ)言L可以被算法B在多項(xiàng)式時(shí)間內(nèi)判定。

非確定圖靈機(jī)(non-deterministicTuringmachine)與確定的圖靈機(jī)的唯一區(qū)別就是狀態(tài)轉(zhuǎn)換函數(shù)

。在確定的圖靈機(jī)中，

把(q,a)映射到唯一的三元組(q’,a’,D)。在非確定的圖靈機(jī)中

把(q,a)映射到多個(gè)三元組的一個(gè)集合，即

(q,a)={(q1,a1,D1)，(q2,a2,D2)，…，(qk,ak,Dk)}，這里k是個(gè)正整數(shù)常數(shù)。確定的圖靈機(jī)可看作非確定的圖靈機(jī)的一個(gè)特例。22用非確定的圖靈機(jī)T識(shí)別語(yǔ)言與確定的圖靈機(jī)操作一樣，它從初始狀態(tài)q0開(kāi)始，如果當(dāng)前狀態(tài)是q，當(dāng)前掃描的字符是a，它要決定三件事，即下一個(gè)狀態(tài)q’，更新的字符a’，和讀寫(xiě)頭的移動(dòng)D。它可以任意選擇集合

(q,a)中的一個(gè)三元組來(lái)變換狀態(tài)，更新字符，和移動(dòng)讀寫(xiě)頭。當(dāng)T進(jìn)入一個(gè)接收狀態(tài)，輸出1，并停止運(yùn)算，表示輸入字符串x被T接收(T(x)=1)。這種情況下，如果我們把非確定的圖靈機(jī)T每步選擇的三元組按序記錄下來(lái)的話，這個(gè)序列稱(chēng)為x的一個(gè)計(jì)算路徑。可能有多條，最短的一條計(jì)算路徑的長(zhǎng)度定義為接受x的時(shí)間復(fù)雜度。只要存在一條x的計(jì)算路徑，可假定這個(gè)非確定的圖靈機(jī)每一步都沿最短的一條計(jì)算路徑正確地選擇集合

(q,a)中的一個(gè)三元組。23定義14.9 一個(gè)語(yǔ)言L稱(chēng)為是被非確定的圖靈機(jī)T在多項(xiàng)式時(shí)間內(nèi)接收的語(yǔ)言，如果它滿足：每一個(gè)x

L都可以被T在多項(xiàng)式時(shí)間內(nèi)接收，即存在一條計(jì)算路徑，其長(zhǎng)度

|x|c，這里，c>0是一個(gè)固定的常數(shù)。每一個(gè)被圖靈機(jī)T在多項(xiàng)式時(shí)間|x|c內(nèi)接收的字符串x都屬于語(yǔ)言L，x

L。定義14.10NP語(yǔ)言類(lèi)(classNP)是所有可以被非確定的圖靈機(jī)在多項(xiàng)式時(shí)間內(nèi)接收的語(yǔ)言的集合，即:NP={L

|L

*并且L

可被一非確定的圖靈機(jī)在多項(xiàng)式時(shí)間內(nèi)接收}。

如果問(wèn)題

對(duì)應(yīng)的語(yǔ)言L(

)屬于NP類(lèi)，那么問(wèn)題

稱(chēng)為NP類(lèi)問(wèn)題。24定理14.3 P

NP。證明：因?yàn)橐粋€(gè)確定的圖靈機(jī)可看作一個(gè)非確定的圖靈機(jī)的一個(gè)特例，只是它的轉(zhuǎn)換函數(shù)

(q,a)只含單個(gè)三元組，所以有P

NP。

多項(xiàng)式檢驗(yàn)算法和NP類(lèi)語(yǔ)言證明L屬于NP類(lèi)時(shí)，需要設(shè)計(jì)一個(gè)非確定的圖靈機(jī)，很不方便。一個(gè)與之等價(jià)的計(jì)算模型是多項(xiàng)式檢驗(yàn)機(jī)(polynomialverifier)。在檢驗(yàn)機(jī)的輸入字符串中，除字符串x以外，還有一個(gè)字符串y，其長(zhǎng)度|y|是|x|的多項(xiàng)式函數(shù)。字符串y是用來(lái)證明x

L的。如果x

L，不可能有字符串y。如果x

L，則一定有字符串y。字符串y稱(chēng)為“證書(shū)”(certificate)。如果我們把x和y合起來(lái)看作輸入字符串的話，T就是一個(gè)確定的圖靈機(jī)。當(dāng)這個(gè)檢驗(yàn)機(jī)T對(duì)輸入字符串x和y進(jìn)行運(yùn)算后輸出T(x,y)=1，我們說(shuō)T接收字符串(x,y)。25定義14.1一個(gè)語(yǔ)言L稱(chēng)為一個(gè)多項(xiàng)式時(shí)間可檢驗(yàn)的語(yǔ)言，如果存在一個(gè)(確定的)圖靈機(jī)T使得x

L

當(dāng)且僅當(dāng)存在一個(gè)字符串y，|y|≤|x|c,使得字符串(x,y)被T在多項(xiàng)式時(shí)間內(nèi)所接收，即T(x,y)=1。這里，c是一個(gè)固定的正數(shù)常數(shù)，y稱(chēng)為x的證書(shū)，而T稱(chēng)為L(zhǎng)的多項(xiàng)式檢驗(yàn)機(jī)。顯然，如果把|y|和|x|總長(zhǎng)看為輸入規(guī)模n’

的話，那么一個(gè)n’的多項(xiàng)式函數(shù)也必定是n

的多項(xiàng)式函數(shù)。不難證明多項(xiàng)式檢驗(yàn)機(jī)的模型與非確定圖靈機(jī)等價(jià)，即一個(gè)多項(xiàng)式時(shí)間可檢驗(yàn)的語(yǔ)言必定可以被一個(gè)非確定圖靈機(jī)在多項(xiàng)式時(shí)間內(nèi)接收，反之亦然。我們略去證明。由于等價(jià)，一個(gè)NP類(lèi)語(yǔ)言L也就是一個(gè)多項(xiàng)式時(shí)間可檢驗(yàn)的語(yǔ)言，反之亦然。26NP-算法(多項(xiàng)式檢驗(yàn)算法)確定的圖靈機(jī)與現(xiàn)代計(jì)算機(jī)模型多項(xiàng)式關(guān)聯(lián)。如果有一個(gè)現(xiàn)代計(jì)算機(jī)的算法A，使得x

L

當(dāng)且僅當(dāng)存在一個(gè)字符串y，|y|≤|x|c,使字符串(x,y)被A在多項(xiàng)式時(shí)間內(nèi)所接收，那么L就是一個(gè)多項(xiàng)式時(shí)間可檢驗(yàn)的語(yǔ)言，算法A稱(chēng)為L(zhǎng)的多項(xiàng)式檢驗(yàn)算法，或NP-算法。如果問(wèn)題

對(duì)應(yīng)的語(yǔ)言L(

)有NP-算法，那么

也就屬于NP類(lèi)了，所以，在證明

是NP類(lèi)問(wèn)題時(shí)，我們只要設(shè)計(jì)一個(gè)多項(xiàng)式檢驗(yàn)算法A去接受L(

)即可。在設(shè)計(jì)NP算法時(shí)，我們要設(shè)計(jì)證書(shū)y并證明，這樣的證書(shū)y存在當(dāng)且僅當(dāng)

(x)=yes，并給出多項(xiàng)式檢驗(yàn)步驟即可。當(dāng)

(x)=no時(shí)，證書(shū)y不存在，對(duì)任何附加輸入y，檢驗(yàn)算法輸出A(x,y)=0或no或不回答。下面我們看2個(gè)例子。(見(jiàn)下頁(yè))27例14.2證明有向圖G(V,E)是否有哈密爾頓回路的判斷問(wèn)題屬于NP類(lèi)。證明：如果G(V,E)有哈密爾頓回路，它通過(guò)每個(gè)頂點(diǎn)正好一次，那么我們可以把這個(gè)回路作為證書(shū)來(lái)驗(yàn)證。顯然，如果G(V,E)有哈密爾頓回路，這個(gè)證書(shū)是存在的。我們用p表示有n個(gè)頂點(diǎn)的序列并作為輸入的證書(shū)。多項(xiàng)式檢驗(yàn)算法的偽碼如下：Hamilton-Cycle-Verification(G(V,E),p) //x

=G(V,E),y=p檢查是否有|p|=|V|檢查p

中每個(gè)頂點(diǎn)是否屬于集合V檢查V中每個(gè)頂點(diǎn)是否在p中出現(xiàn)，并且只出現(xiàn)一次檢查從p中每個(gè)頂點(diǎn)到下個(gè)頂點(diǎn)是否是E中一條邊檢查從p的最后一個(gè)頂點(diǎn)到p的第一個(gè)頂點(diǎn)是否是E中一條邊如果第1步到第5步的答案都是yes，那么輸出1，否則輸出0End28

29簡(jiǎn)單來(lái)講，NP完全(NPC)問(wèn)題就是NP類(lèi)中最難的問(wèn)題。如果有一個(gè)NPC問(wèn)題有多項(xiàng)式算法，那么所有NP類(lèi)問(wèn)題都會(huì)有多項(xiàng)式算法。定義14.12一個(gè)語(yǔ)言L被稱(chēng)為NPC語(yǔ)言，如果它滿足：(1)L

NP;

(2)NP類(lèi)中任何一個(gè)語(yǔ)言L’可多項(xiàng)式歸約到L，即L’

p

L。註評(píng):如果一個(gè)語(yǔ)言L只滿足第2個(gè)條件，那么L被稱(chēng)為一個(gè)NP難(NP-hard)語(yǔ)言。如果一個(gè)問(wèn)題

所對(duì)應(yīng)的語(yǔ)言L(

)是NPC或NP難語(yǔ)言，那么問(wèn)題

則對(duì)應(yīng)地被稱(chēng)為是一個(gè)NPC問(wèn)題或NP難問(wèn)題。一個(gè)NPC問(wèn)題顯然也是一個(gè)NP難問(wèn)題。定義14.13

NPC語(yǔ)言類(lèi)是所有NPC語(yǔ)言的集合，簡(jiǎn)記為NPC。即: NPC={L|L

是一個(gè)NPC語(yǔ)言}。通常，NPC也用來(lái)代表所有NPC問(wèn)題的集合3.NPC語(yǔ)言類(lèi)和NPC問(wèn)題

30定理14.4

任何一個(gè)NPC語(yǔ)言有多項(xiàng)式判定算法當(dāng)且僅當(dāng)P=NP。證明：如果某個(gè)NPC語(yǔ)言L有多項(xiàng)式算法來(lái)判定，那么L

P。又因?yàn)長(zhǎng)

NPC，任何一個(gè)NP語(yǔ)言L’可以多項(xiàng)式歸約到L，即L’

p

L，由定理14.1，L’可以被一個(gè)多項(xiàng)式算法所判定，所以有L’

P。這就意味著NP

P，但由定理14.3，P

NP，所以得到P=NP。反之，如果有P=NP，那么因?yàn)镹PC

NP=P，所以任何一個(gè)NPC語(yǔ)言L有多項(xiàng)式算法判定。

推論14.5

如果一個(gè)NPC語(yǔ)言L沒(méi)有多項(xiàng)式算法，那么P

NPC=

。證明：為用反證法，我們假設(shè)L沒(méi)有多項(xiàng)式判定算法，但是P

NPC

。那么必有一語(yǔ)言L’

P

NPC。這表明L’有多項(xiàng)式判定算法并且屬于NPC。從定理14.4知，P=NP，所以L

NPC

NP=P。那么，L也必定有多項(xiàng)式算法，這與“L沒(méi)有多項(xiàng)式算法”矛盾。

31P、NP、和NPC之間可能的關(guān)系到目前為止，人們還不知道是否有一個(gè)NPC語(yǔ)言L可以被一多項(xiàng)式算法所判定，也不能證明任何一個(gè)NPC語(yǔ)言L不可能被一多項(xiàng)式算法所判定。因此，如下圖(14-4)所示，集合P，NP，和NPC之間的關(guān)系有兩種，但大部分人相信第二種(圖14-4(b))，但有待證明。PNPNPC(a)P=NPC=NPP=NPC=NP(b)P

NPC=

32第一個(gè)NPC問(wèn)題歷史上第一個(gè)被證明的NPC問(wèn)題是布爾表達(dá)式的可滿足性問(wèn)題。一個(gè)布爾表達(dá)式就是用邏輯運(yùn)算把布爾變量連結(jié)起來(lái)的表達(dá)式，例如，

=((x1

x2)

((

x1

x3)

x4))

(

x2

x3)。如有一組變量的賦值使表達(dá)式

=1，則稱(chēng)該表達(dá)式是可被滿足的。例如，若賦以x1=0，x2=0，x3=1，x4=1，則上面表達(dá)式的值為:

=((x1

x2)

((

x1

x3)

x4))

(

x2

x3)=((0

0)

((

0

1)

1))

(

0

1)=(0

(1

1))

(1

1)=(0

1)

1=1。

所以上面例子中表達(dá)式是可以被滿足的。

如果不論怎樣給變量賦值，表達(dá)式的值總是為0，那么稱(chēng)該表達(dá)式為不可被滿足。例如

=(x1

x2)

x1

x2

就是一個(gè)不可被滿足的布爾表達(dá)式。33布爾表達(dá)式的可滿足性(FormulaSatisfiability)問(wèn)題，簡(jiǎn)稱(chēng)為SAT問(wèn)題，就是判斷任一個(gè)給定布爾表達(dá)是否可被滿足。StephenCook在1971年證明了SAT問(wèn)題是個(gè)NPC問(wèn)題，稱(chēng)為Cook定理。這個(gè)定理有著劃時(shí)代的意義，因?yàn)樗C明了在NP類(lèi)中確實(shí)存在象SAT這樣的NPC問(wèn)題，而且而且大大地簡(jiǎn)化了證明和發(fā)現(xiàn)其他的NPC問(wèn)題的工作，現(xiàn)在，當(dāng)我們需要證明一個(gè)新的問(wèn)題

是NPC問(wèn)題時(shí)，只需遵循下面的方法。新問(wèn)題

是NPC問(wèn)題的證明步驟:證明

NP選一個(gè)已被證明的NPC問(wèn)題

’并證明

’

p

。正確性：因?yàn)?/p>

’

NPC，所以NP類(lèi)中任一個(gè)問(wèn)題

’’可多項(xiàng)式歸約到

’，即

’’

p

’。又因?yàn)?/p>

’

p

，所以

’’也可多項(xiàng)式歸約到

，

’’

p

，盡管這個(gè)歸約需要二步。

34Cook定理的證明比較長(zhǎng)，我們略去這個(gè)證明，但是我們選用另外一個(gè)NP類(lèi)問(wèn)題作為第一個(gè)NPC問(wèn)題來(lái)證明。電路的可滿足性問(wèn)題(Circuit-SAT)考慮組合電路C，它由與門(mén)、或門(mén)、和非門(mén)組成。電路C有若干個(gè)輸入信號(hào)，每個(gè)信號(hào)可取0或1。當(dāng)一組輸入信號(hào)經(jīng)過(guò)電路C后，電路產(chǎn)生一個(gè)0或1的輸出信號(hào)。如果有一組輸入信號(hào)(輸入變量)使得輸出信號(hào)的值是1，那么這個(gè)電路被稱(chēng)為可滿足的，否則為不可滿足。電路的可滿足性問(wèn)題就是對(duì)任一給定電路C，判斷它是否可滿足。用<C>表示電路C的一個(gè)字符串編碼，那么，電路的可滿足性問(wèn)題對(duì)應(yīng)的語(yǔ)言可定義為

Circuit-SAT={<C>|電路C可被滿足}。下圖(14-5(a)和(b))分別給出了一個(gè)可滿足和不可滿足的電路實(shí)例。35x31x1x211111110(a)

一個(gè)可滿足的電路實(shí)例x1x2x3(b)

一個(gè)不可滿足的電路實(shí)例定理14.6

語(yǔ)言Circuit-SAT屬于NPC類(lèi)。證明：我們先為語(yǔ)言Circuit-SAT設(shè)計(jì)一個(gè)NP算法。每個(gè)邏輯門(mén)只有一個(gè)輸出值并且是其它門(mén)的輸入，我們把它們之間的連接稱(chēng)為一根連線。當(dāng)輸入變量給定時(shí)，每條連線上的二進(jìn)制值及C的輸出值就定了。假設(shè)x是電路C的編碼，其長(zhǎng)度|x|與輸入變量的個(gè)數(shù)，邏輯門(mén)的個(gè)數(shù)，及連線的個(gè)數(shù)的總和成正比(或多項(xiàng)式函數(shù))。電路C滿足時(shí)，證書(shū)y包含所有連線，所有輸入和輸出變量上的二進(jìn)制值。顯然有c

>0使|y|≤|x|c。NP-算法如下:(見(jiàn)下頁(yè))36定理14.6 的證明(繼續(xù)1)Circuit-SAT-Verification(<C>,y)1 對(duì)x=<C>中描述的每個(gè)門(mén)g做如下操作:1.1 在y中找出g的所有輸入值和它的輸出值1.2 檢查門(mén)g的輸入值和輸出值之間的關(guān)系是否符合門(mén)g的定義1.3 如果不符合門(mén)g的定義，則輸出0后退出算法，否則繼續(xù)2 在y中找出C的輸出值并檢驗(yàn)是否為13 如果C的輸出值是1，則輸出1，否則輸出0End顯然，這個(gè)算法中每一步都可以在多項(xiàng)式時(shí)間內(nèi)完成，因此，語(yǔ)言Circuit-SAT屬于NP類(lèi)。下面證明Circuit-SAT滿足NPC的笫2個(gè)條件。證明任何NP語(yǔ)言L

可以多項(xiàng)式歸約到語(yǔ)言circuit-SAT。(接下頁(yè))37定理14.6 的證明(繼續(xù)2)因?yàn)長(zhǎng)

NP，則有多項(xiàng)式檢驗(yàn)機(jī)T對(duì)字符串x和證書(shū)y進(jìn)行識(shí)別判斷。設(shè)x=x1x2…xn，y=y1y2…ym，m

≤nc。x

L當(dāng)且僅當(dāng)T在M=(n+m)k步內(nèi)可輸出1。這里，k是一個(gè)常數(shù)。假設(shè)檢驗(yàn)機(jī)T的讀寫(xiě)帶上的格子從0開(kāi)始編號(hào)，這n+m個(gè)輸入字符放在從0到n+m-1的格子中。其余的格子(從m+n

到M)中初始放0。假設(shè)輸出符號(hào)t放在編號(hào)為n+m的格子中。因?yàn)門(mén)在M

步內(nèi)停機(jī)，它不會(huì)掃描到第M號(hào)格子之后的格子。我們證明，可以在多項(xiàng)式時(shí)間內(nèi)構(gòu)造一個(gè)Circuit-SAT的實(shí)例C

使得檢驗(yàn)機(jī)T在M

步內(nèi)輸出1當(dāng)且僅當(dāng)C

可被滿足。(A)

我們先為電路C構(gòu)造輸入變量如下：(A.1)構(gòu)造M=(n+m)k個(gè)輸入變量，u0,u2,…,uM-1，順序?qū)?yīng)T上的頭M個(gè)格子上字符。(接下頁(yè))38定理14.6 的證明(繼續(xù)3)(A.2)構(gòu)造r=

lgM

個(gè)額外的輸入變量v1,v2,…,vr。二進(jìn)制數(shù)v[1..r]=<v1,v2,…,vr>

指出當(dāng)前讀寫(xiě)頭的位置，即地址，初始值為0。(A.3)假設(shè)T有W個(gè)不同狀態(tài)，q0，q1，q2，…，qW-1，則構(gòu)造d=

lgW

個(gè)輸入變量，w1,w2,…,wd。二進(jìn)制數(shù)W[1..d]=<w1,w2,…,wd>表示當(dāng)前狀態(tài)，初始值為0，初始狀態(tài)為q0。W是常數(shù)，d為常數(shù)。(A.2)和(A.3)構(gòu)造的輸入變量是內(nèi)部用的，輸入值是固定的。(B) 對(duì)檢驗(yàn)機(jī)T的每一步，構(gòu)造一層電路，使得各變量通過(guò)后變化如下：(a)<u0,u1,…,uM-1>

等于檢驗(yàn)機(jī)T一步操作后讀寫(xiě)帶上應(yīng)有的值；(b)<w1,w2,…,wd>

等于檢驗(yàn)機(jī)T

一步操作后新的狀態(tài)；(c)<v1,v2,…,vr>

等于檢驗(yàn)機(jī)T

一步操作后新的地址。所以，每層的輸出變量的個(gè)數(shù)和含義與輸入變量相同，但數(shù)值不同。這一層的構(gòu)造是通用的，一共構(gòu)造M層。圖(14-6)顯示了第一層的構(gòu)造。見(jiàn)p41，具體解釋如下。39定理14.6 的證明(繼續(xù)4)

在u0,u1,…,uM-1中選取地址為k=v[1..r]

的變量uk(0

k

M-1)。設(shè)

uk

=a(0或1)。地址

k

對(duì)應(yīng)當(dāng)前讀寫(xiě)頭所指的讀寫(xiě)帶上格子的編號(hào)。變量a就是這個(gè)格子里的字符。如圖，這可以用多路復(fù)用器(MUX)實(shí)現(xiàn)，需要的邏輯門(mén)和連線的個(gè)數(shù)是O(M)。MUX把變量a從地址

k取出后送到圖左邊的電路E。(2) 由變量a以及狀態(tài)q的變量W[1..d]，電路

E計(jì)算檢驗(yàn)機(jī)T的轉(zhuǎn)換函數(shù)

(q,a)=(q’,a’,D)中三元組的三個(gè)函數(shù)值：(2.1) (q’,a’,D)中的a’。從(q,a)到a’的函數(shù)對(duì)應(yīng)一個(gè)真值表，可用門(mén)電路來(lái)實(shí)現(xiàn)，含在電路E中，并且邏輯門(mén)和連線的個(gè)數(shù)是常數(shù)。圖中

是輸出信號(hào)。

=1表示a’=

(a)，而

=0表示a’=a。

通過(guò)DEMUX電路到達(dá)原地址k的位置，與輸入信號(hào)

a會(huì)合于一個(gè)MUX。(接下頁(yè))40定理14.6 的證明(繼續(xù)5) MUX根據(jù)

=1或

=0，輸出a’=

a或a’=

a。這個(gè)MUX需要的邏輯門(mén)和連線個(gè)數(shù)是常數(shù)。DEMUX需要的邏輯門(mén)和連線的個(gè)數(shù)是O(M)。(2.2) 計(jì)算(q’,a’,D)中的狀態(tài)q’

設(shè)q’=W[1..d]=<w’1,w’2,…,w’d>，我們?yōu)槊總€(gè)輸出變量w’1,w’2,…,w’d分別構(gòu)造一個(gè)真值表。每個(gè)真值表可以用門(mén)電路來(lái)實(shí)現(xiàn)，并且所用邏輯門(mén)和連線的個(gè)數(shù)也是常數(shù)。q’=<w’1,w’2,…,w’d>由電路E直接輸出到下一層電路。(2.3) 三元組(q’,a’,D)中的D。這一步計(jì)算新地址，由原地址減1，或加1，或加0得到，分別對(duì)應(yīng)

D=L，R，N。所以，D有兩個(gè)比特，輸出給一個(gè)MUX來(lái)做出選擇。計(jì)算D需要的邏輯門(mén)和連線個(gè)數(shù)與d+1成正比，是常數(shù)。這個(gè)MUX需要的邏輯門(mén)和連線個(gè)數(shù)與r=

lgM

成正比。原地址減1，加1，或加0的計(jì)算需邏輯門(mén)和連線的個(gè)數(shù)也是O(r)。(接下頁(yè))4101MUXu101MUXuM-101MUX

uM-1u0u1MUX由狀態(tài)轉(zhuǎn)換函數(shù)得到真值表后構(gòu)造的電路Ew1

w2…wd(初態(tài)=q0)aDEMUX

w’1

w’2…w’du0v1

v2…vr0rr+1-1MUX更新值

0122信號(hào)Dv’1

v’2…v’r圖14-6

電路的第一層構(gòu)造示意定理14.6 的證明(繼續(xù)6)新地址的

r個(gè)變量<v’1,v’2,…,v’r>由這個(gè)MUX輸出給下一層電路42定理14.6 的證明(繼續(xù)7)

其余M-1層與第一層的構(gòu)造相同，輸入狀態(tài)和地址由上一層的輸出得到。另外，如當(dāng)前狀態(tài)是終止?fàn)顟B(tài)qf時(shí)，對(duì)任何輸入變量a，規(guī)定

(qf,a)=(qf,a,N)。也就是說(shuō)保持所有變量不變(C) 構(gòu)造了M層電路后，再造一層電路以輸出變量un+m。這只需O(n+m)個(gè)邏輯門(mén)和連線。下圖(14-7)顯示了最后一層構(gòu)造。w1

w2…wd

v1

v2…vru0

u1…un+mun+m+1

un+m+2…uM-1t輸出變量

1從上述構(gòu)造可知，該電路忠實(shí)地摸擬檢驗(yàn)機(jī)T的檢驗(yàn)過(guò)程。所以，檢驗(yàn)機(jī)T在M步內(nèi)輸出1當(dāng)且僅當(dāng)所構(gòu)造電路可被滿足。因?yàn)檎麄€(gè)電路所含的邏輯門(mén)的個(gè)數(shù)或?qū)Ь€個(gè)數(shù)的總和不超過(guò)O(M2)，所以有L

p

Circuit-SAT。

43若干著名NPC問(wèn)題的證明這一節(jié)我們介紹若干個(gè)早期被證明的最著名的NPC問(wèn)題。下圖(14-8)標(biāo)出了我們要討論的NPC問(wèn)題以及與之關(guān)聯(lián)的歸約樹(shù)。因?yàn)樽C明這些問(wèn)題屬于NP類(lèi)很容易，我們只證明多項(xiàng)式歸約部分。Circuit-SATSAT3-SATCliqueVertex-CoverHamilton-CycleTSPSubset-SumSet-Partitionk-Colorability44若干著名NPC問(wèn)題的證明順序circuit-SAT

pSAT 45SAT

p3-SAT 473-SAT

pclique 51clique

pvertex-cover 55vertex-cover

pHamilton-cycle 58Hamilton-Cycle

pTSP 663-SAT

psubset-sum 68subset-sum

pset-partition 743-SAT

p

k-colorability 7645

46x1x2x3f1=(x4

x3)1342x4x5x6x7f2=(x5

x1

x2)f3=(x6

x1

x2

x4)f4=(x7

x5

x6)

=x7

f1

f2

f3

f4

=x7

(x4

x3)(x5

x1

x2)(x6

x1

x2

x4)(x7

x5

x6)例因?yàn)闉檫壿嬮T(mén)i而構(gòu)造的表達(dá)式fi正確地定義了其輸出和輸入變量之間的關(guān)系，所以容易看出電路C可被滿足當(dāng)且僅當(dāng)

可被滿足。另外，構(gòu)造表達(dá)式

的時(shí)間顯然是門(mén)的個(gè)數(shù)和連線個(gè)數(shù)的多項(xiàng)式函數(shù)，所以有Circuit-SAT

p

SAT。472. SAT問(wèn)題

p

3-SAT問(wèn)題3-SAT是SAT的一個(gè)子問(wèn)題，因?yàn)楸磉_(dá)式

必須是一個(gè)3-CNF。CNF(conjunctiveformalform)稱(chēng)為合取范式，它由一系列子句(Clause)用與(AND)運(yùn)算連結(jié)而成，而每個(gè)子句由若干個(gè)文字用或(OR)運(yùn)算連結(jié)而成。一個(gè)文字(literal)是指一個(gè)布爾變量或者變量的非。如果每個(gè)子句正好有3個(gè)文字，則表達(dá)式

稱(chēng)為3-CNF。例如:

=(x1

x1

x2)

(x3

x2

x4)

(

x1

x3

x4)。3-SAT問(wèn)題是判斷一個(gè)給定的3-CNF的表達(dá)式

是否可滿足。下面，我們說(shuō)明如何把SAT問(wèn)題的一個(gè)實(shí)例多項(xiàng)式轉(zhuǎn)換為一個(gè)

3-SAT的實(shí)例。我們用下面的例子來(lái)解釋。假設(shè)SAT問(wèn)題的一個(gè)實(shí)例是：

=((x1

x2)

((

x1

x3)

x4))

(

x2

x3)多項(xiàng)式轉(zhuǎn)換算法如下：(接下頁(yè))48多項(xiàng)式轉(zhuǎn)換算法(繼續(xù)1)如下圖(14-10)所示，

可以用一個(gè)二叉樹(shù)來(lái)表示，用一個(gè)新變量代表每個(gè)內(nèi)結(jié)點(diǎn)運(yùn)算后的輸出變量。這一步可在多項(xiàng)式時(shí)間內(nèi)完成。

=((x1

x2)

((

x1

x3)

x4))

(

x2

x3)。

x2x3

x1x3x4x1x2y1y2y3y4y5y6

’=y1

(y1

(y2

y3))

(y2

(y4

y5)

(y3

(

x2

x3))

(y4

(x1

x2))

(y5

(y6

x4))

(y6

(

x1

x3))(2) 為每個(gè)內(nèi)結(jié)點(diǎn)構(gòu)造一個(gè)布爾表達(dá)式來(lái)表示它的輸出變量和它的兩個(gè)輸入變量之間的關(guān)系。然后，把所有這些小表達(dá)式以及根結(jié)點(diǎn)的輸出變量用與的運(yùn)算串連起來(lái)得到表達(dá)式

’

(上圖)。(接下頁(yè))49多項(xiàng)式轉(zhuǎn)換算法(繼續(xù)2)(3)

為

’中每個(gè)小表達(dá)式構(gòu)造一真值表，然后找出一個(gè)3-CNF表達(dá)式來(lái)實(shí)現(xiàn)這個(gè)真值表。我們以本例中表達(dá)式y(tǒng)1

(y2

y3)為例說(shuō)明。y1y2y3y1

(y2

y3)00010011010101101000101011001111由這個(gè)真值表，可得到一個(gè)等于0的析取范式(DNF):(

y1

y2

y3)

(y1

y2

y3)

(y1

y2

y3)

(y1

y2

y3)。(接下頁(yè))50多項(xiàng)式轉(zhuǎn)換算法(繼續(xù)3)析取范式(DNF)為：(

y1

y2

y3)

(y1

y2

y3)

(y1

y2

y3)

(y1

y2

y3)。再用德摩根(DeMorgan)定理把這個(gè)析取范式變?yōu)榈扔?的3-CNF:(y1

y2

y3)

(

y1

y2

y3)

(

y1

y2

y3)

(

y1

y2

y3)。因?yàn)檎嬷当碇械扔?的行最多是8個(gè)，所以這個(gè)3-CNF中的子句最多有8個(gè)，因此在線性時(shí)間里可以完成對(duì)

’中所有小表達(dá)式的變換，即把所有小表達(dá)式變換為等價(jià)的3-CNF表達(dá)式。把

’中每個(gè)小表達(dá)式換為等價(jià)的3-CNF表達(dá)式后得到的表達(dá)式

’’就是我們從SAT問(wèn)題一個(gè)實(shí)例構(gòu)造得到的3-CNF表達(dá)式。顯然，

’’的構(gòu)造可在多項(xiàng)式時(shí)間內(nèi)完成。又因?yàn)?/p>

’’可被滿足當(dāng)且僅當(dāng)’可被滿足，而

’可被滿足當(dāng)且僅當(dāng)

可被滿足。因此有SAT問(wèn)題

p

3-SAT問(wèn)題。513. 3-SAT問(wèn)題

p

Clique問(wèn)題圖G的一個(gè)子圖如果是個(gè)完全圖，則稱(chēng)為一個(gè)團(tuán)(clique)。給定圖G，找它的一個(gè)最大的團(tuán)是個(gè)優(yōu)化型問(wèn)題。對(duì)應(yīng)的判斷型問(wèn)題是:給定圖G和正整數(shù)k，G是否含有一個(gè)k-clique(由k個(gè)頂點(diǎn)形成的團(tuán))？注意，這里的k不是常數(shù)。否則，窮舉搜索一個(gè)有常數(shù)k個(gè)頂點(diǎn)的團(tuán)只需(nk)時(shí)間。下面解釋?zhuān)绾伟?-SAT問(wèn)題多項(xiàng)式歸約到Clique問(wèn)題。構(gòu)造k-clique問(wèn)題實(shí)例的多項(xiàng)式算法假設(shè)3-SAT的一個(gè)實(shí)例是：

=C1

C2…

Cm。子句Ci

(1

i

m)

中3個(gè)文字是li,1，li,2，li,3。構(gòu)造對(duì)應(yīng)的k-clique問(wèn)題實(shí)例，圖G(V,E)，的步驟如下：構(gòu)造3m個(gè)頂點(diǎn)，分別對(duì)應(yīng)3m個(gè)文字，即V={li,1，li,2，li,3|1

k

m}。每個(gè)子句對(duì)應(yīng)的3個(gè)點(diǎn)為一小組，一共m組。(接下頁(yè))52構(gòu)造k-clique問(wèn)題實(shí)例的多項(xiàng)式算法(繼續(xù)1)(2) 邊的集合E的組成如下：同一組中3個(gè)點(diǎn)之間沒(méi)有邊，不同組的任何兩點(diǎn)之間，只要不代表互補(bǔ)的兩個(gè)文字，構(gòu)造一條邊。這里，互補(bǔ)是指一個(gè)變量和它的非。

下圖(14-12)顯示了一個(gè)從表達(dá)示轉(zhuǎn)換為一個(gè)圖的例子。C2=

x1

x2

x3C3=x1

x2

x3

x2x1C1=x1

x2

x3

x3

x1x2x3表達(dá)式：

=(x1

x2

x3)(

x1

x2

x3)(x1

x2

x3)x1

x2

x3構(gòu)造的圖接下頁(yè)53構(gòu)造k-clique問(wèn)題實(shí)例的多項(xiàng)式算法(繼續(xù)2)(3)

構(gòu)造好圖G以后，置k=m，則轉(zhuǎn)換完成。上面轉(zhuǎn)換顯然可在多項(xiàng)式時(shí)間內(nèi)完成?，F(xiàn)在證明

可被滿足當(dāng)且僅當(dāng)所構(gòu)造的圖有一個(gè)m-clique。假設(shè)

可被滿足。我們從每個(gè)子句中選一個(gè)賦值為1的文字，一共m個(gè)文字。這m個(gè)文字對(duì)應(yīng)的m個(gè)頂點(diǎn)一定形成一個(gè)m-clique。理由如下。因?yàn)檫@m個(gè)頂點(diǎn)對(duì)應(yīng)的文字賦值為1，這m個(gè)文字中不可能有互補(bǔ)的兩個(gè)文字。又因?yàn)樗鼈兎謱賛個(gè)不同的小組，所以任兩個(gè)頂點(diǎn)間一定有邊。所以這m個(gè)頂點(diǎn)形成一個(gè)m-clique。假設(shè)所構(gòu)造圖有一個(gè)m-clique。(接下頁(yè))54構(gòu)造k-clique問(wèn)題實(shí)例的多項(xiàng)式算法(繼續(xù)3)假設(shè)所構(gòu)造圖有一個(gè)m-clique。那么，這m個(gè)頂點(diǎn)必定分屬于m個(gè)不同的小組，它們對(duì)應(yīng)的m個(gè)文字必分屬于不同的子句。我們可將這m個(gè)文字賦以1。因?yàn)檫@m個(gè)文字中任意兩個(gè)之間不可能互補(bǔ)，所以這樣的賦值不會(huì)產(chǎn)生矛盾。然后把已賦值的文字的非賦值為0。這樣一來(lái)，每個(gè)字句中至少有一文字被賦以1，所以表達(dá)式可被滿足。對(duì)這k=m個(gè)所選文字以及它們的非賦值以后，也許還有沒(méi)被賦值的變量，我們可將這樣的變量及它的非分別賦以1和0。以上證明了表達(dá)式

可被滿足當(dāng)且僅當(dāng)所構(gòu)造圖有一個(gè)k-clique。因此，3-SAT問(wèn)題

p

Clique問(wèn)題。55

56

(a){a,b,e,f}是圖G的一個(gè)團(tuán)acfdegb(b){c,d,g}是圖G’的一個(gè)復(fù)蓋acfdegb

57

585. vertex-Cover

p

Hamilton-Cycle假設(shè)vertex-cover的特例是圖G和k，多項(xiàng)式轉(zhuǎn)換算法構(gòu)造圖G’如下。第1步: 對(duì)應(yīng)于G中每一條邊(u,v)，構(gòu)造一個(gè)小圖Wuv，稱(chēng)為小器具。下圖(14-14(a))顯示了這個(gè)構(gòu)造。uv,1uv,2vu,1vu,2(a)Wuv

的構(gòu)造uv,1uv,2vu,1vu,2(b)

第1種一次穿越uv,1uv,2vu,1vu,2(c)

第2種一次穿越uv,1uv,2vu,1vu,2(d)

兩次穿越Wuv含12個(gè)點(diǎn)。其中有標(biāo)記的4個(gè)點(diǎn)與圖中其他點(diǎn)相連。如果它被G’的一條哈密爾頓回路穿過(guò)的話，只能有三種可能。圖中(b)(c)(d)顯示了這三種可能的情況。59

uabc(a)

頂點(diǎn)u有3條邊(b)

Du把與u關(guān)聯(lián)的邊所對(duì)應(yīng)的小器具串連起來(lái)ua,1ua,2au,1au,2Wua

ub,1ub,2bu,1bu,2Wub

uc,1uc,2cu,1cu,2Wuc

60幾點(diǎn)說(shuō)明：Du提供了一條從(uv1,1)進(jìn)，到(uvd,2)出的，穿過(guò)所有與u關(guān)聯(lián)的邊所對(duì)應(yīng)的小器具的路徑。在穿過(guò)每一個(gè)小器具時(shí)，可選擇穿過(guò)所有12個(gè)點(diǎn)或只穿越6個(gè)點(diǎn)。我們用Pu表示這條路徑。對(duì)G中一條邊(u,v)來(lái)說(shuō)，Wuv

與Wvu是同一個(gè)小器具，在G’中只出現(xiàn)一次。但對(duì)Du和Dv說(shuō)，它們都要分別把Wuv

串連一次，不同的是，Dv連的口子是(vu,2)和(vu,1)，而Du連的口子是(uv,2)和(uv,1)。這也就是說(shuō)，u和v各自用Wuv不同一側(cè)的兩個(gè)口子。路徑Pu也許會(huì)在哈密爾頓回路中用到，也許不用。如果它是哈密爾頓回路中一部分，在它穿越每個(gè)小器具Wuv時(shí)，是經(jīng)過(guò)12個(gè)點(diǎn)還是6個(gè)點(diǎn)要看是否有另外一條路徑Pv穿過(guò)Wuv。下頁(yè)圖(14-16)顯示了一個(gè)有4個(gè)頂點(diǎn)和4條邊的圖G，以及為它所構(gòu)造的4個(gè)小器具和4條路徑。對(duì)應(yīng)頂點(diǎn)u的路徑的兩端用Pu和P’u標(biāo)注。61uabc圖Gua,1ua,2au,1au,2Wua

ub,1ub,2bu,1bu,2Wub

uc,1uc,2cu,1cu,2Wuc

ba,1ba,2ab,1ab,2Wba

Pu

P’u

Pa

P’aPb

P’b

Pc

P’c

圖14-1662第3步，在G’中加入k個(gè)點(diǎn)，s1,s2,…,sk。然后將點(diǎn)si

(1

i

k)

與每一個(gè)Du

(u

G)的兩頭相連。下圖(14-17)顯示了，當(dāng)k=2時(shí)，在圖14-16基礎(chǔ)上完成這一步之后的圖。這一步之后，G’構(gòu)造完成。aWua

Wub

Wuc

ubc圖GWba

Pu

P’uPa

P’aPb

P’bPc

P’cs1s2與s1相同圖14-1763

64Wua

Wub

Wuc

uabc圖GWba

Pu

P’uPb

Pb’

s1s2對(duì)應(yīng)于2-cover{u,b}的哈密爾頓回路假設(shè)G’中有一條哈密爾頓回路，從點(diǎn)s1開(kāi)始。因?yàn)槊總€(gè)頂點(diǎn)正好出現(xiàn)一次，我們可假定頂點(diǎn)s1,s2,…,sk,

s1順序在回路中出現(xiàn)。既使不按這個(gè)順序，把它們交換為這個(gè)順序后仍然是一條哈密爾頓回路。(接下頁(yè))轉(zhuǎn)換算法的正確性證明(繼續(xù)1)65轉(zhuǎn)換算法的正確性證明(繼續(xù)2)我們用<Pi,P’i>表示點(diǎn)si和s(i+1)modk

(1

i

k)之間的一段路徑。由小器具的構(gòu)造知，<Pi,P’i>必定是對(duì)應(yīng)于G中某個(gè)點(diǎn)u的路徑Pu。我們把點(diǎn)u選為G的一個(gè)復(fù)蓋中的點(diǎn)。這樣，我們可一共選出k個(gè)點(diǎn)，形成k個(gè)點(diǎn)的集合S。我們說(shuō)，S是G的一個(gè)k-cover。這是因?yàn)镚’中每個(gè)小器具都被回路中某個(gè)路徑Pu穿過(guò)，那么這個(gè)小器具對(duì)應(yīng)的G中的邊一定關(guān)聯(lián)于頂點(diǎn)u。所以G中的每條邊一定關(guān)聯(lián)于頂點(diǎn)S中某個(gè)點(diǎn)，S是G的一個(gè)k-cover。這樣，我們就證明了，G有一個(gè)k-cover當(dāng)且僅當(dāng)G’有哈密爾頓回路。因?yàn)闃?gòu)造圖G’只需多項(xiàng)式時(shí)間，所以有Vertex-Cover

pHamilton-Cycle。66Hamilton-cycle

pTSP給定一個(gè)加權(quán)的完全圖G，TSP問(wèn)題(貨郎擔(dān)問(wèn)題)，是找出G中一條總權(quán)值最小的哈密爾頓回路，稱(chēng)為貨郎擔(dān)回路。判斷型問(wèn)題是，G中是否存在一條總權(quán)值不大于k的哈密爾頓回路？多項(xiàng)式轉(zhuǎn)換算法假設(shè)Hamilton-Cycle問(wèn)題的一個(gè)實(shí)例是圖G(V,E)。轉(zhuǎn)換算法構(gòu)造一個(gè)TSP的實(shí)例，包括圖G’(V’,E’)和實(shí)數(shù)k。第1步，G’

G，也就是復(fù)制一個(gè)G，V’

V,E’

E。第2步，賦以當(dāng)前E’中的每條邊(u,v)的權(quán)值為0，即w(u,v)

0。第3步，如果(u,v)

E’，u

v，則把(u,v)加到E’中，并賦以權(quán)值1，即w(u,v)

1。這樣一來(lái)，G’(V’,E’)就是一個(gè)加權(quán)的完全圖。第4步，置k=n。轉(zhuǎn)換完成。(接下頁(yè))67多項(xiàng)式轉(zhuǎn)換算法(繼續(xù))下圖(14-19)給出了一個(gè)構(gòu)造G’的例子。其中第3步中加的邊用粗線標(biāo)出。dabcedabce(a)Hamilton-Cycle問(wèn)題中的圖G(b)

TSP問(wèn)題中的圖G’0000000111顯然，圖G有一條哈密爾頓回路當(dāng)且僅當(dāng)G’中有一條總長(zhǎng)為0的貨郎擔(dān)回路。所以有Hamilton-Cycle

pTSP。687. 3-SAT

pSubset-Sum假設(shè)S是有n個(gè)正整數(shù)的集合。Subset-Sum(子集和)問(wèn)題是問(wèn)：能否從S中找出一個(gè)子集A使得A中所有整數(shù)之和恰好等于一個(gè)給定的目標(biāo)值t。多項(xiàng)式轉(zhuǎn)換算法假設(shè)

是一個(gè)含有n個(gè)變量和m個(gè)子句的3-CNF。設(shè)這n個(gè)變量為x1，x2，…，xn,這m個(gè)子句為C1，C2，…，Cm。我們將構(gòu)造集合S和目標(biāo)值t。S

有2n+2m

個(gè)數(shù)，每個(gè)整數(shù)有n+m位。這n+m位，從最高位(最左一位)到最低位依次對(duì)應(yīng)著x1，x2，…，xn和C1，C2，…，Cm。下面是構(gòu)造的具體步驟。(接下頁(yè))69多項(xiàng)式轉(zhuǎn)換算法(繼續(xù)1)第1步，為每個(gè)變量xi

(1

i

n)構(gòu)造兩個(gè)整數(shù)，vi和v’i，分別對(duì)應(yīng)xi和

xi。它們的值是這樣決定的：在對(duì)應(yīng)于xi

的那一位上，vi和v’i都是1，而對(duì)應(yīng)于其他的xj

(j

i)的位上都是0。在對(duì)應(yīng)于Ck

(1

k

m)的那一位上，如果xi

Ck，那么vi的值為1，否則為0。同樣的，如果

xi

Ck，那么在對(duì)應(yīng)于Ck的位上，v’i的值為1，否則為0。這一步一共為集合S

構(gòu)造了2n個(gè)數(shù)。以

=(x1

x2

x3)

(

x1

x2

x3)

(x1

x2

x3)為例，下圖(14-20)的上半部分顯示了這些整數(shù)的構(gòu)造。這個(gè)3-CNF有3個(gè)變量和3個(gè)子句，所以，這一部分一共構(gòu)造了6個(gè)整數(shù)，每個(gè)整數(shù)都是6位數(shù)。70

x1x2x3C1C2C3v1=100101v’1=100010v2=010101v’2=010010v3=001001v’3=001110