計算機算法基礎(chǔ) 第2版 課件 第14章 NP-完全問題

1第14

章

NP-完全問題序言

2預(yù)備知識

4P和NP語言類

20NPC語言類和NPC問題

29第一個NPC問題

32若干著名NPC問題的證明

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

NP。如果NPC中有一個有多項式算法，那么所有NP問題都有多項式算法。反之，如有一個沒有多項式算法，那么所有NPC問題都沒有多項式算法。P

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

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

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

中的一個符號?？瞻椎母褡佑商厥夥朆表示。Q是個有限個狀態(tài)的集合。有限狀態(tài)控制器在任一時刻處于Q中的一個狀態(tài)q并控制讀寫頭的讀寫操作。一開始在初始狀態(tài)q0。(接下頁)5如果有限狀態(tài)控制器當前的狀態(tài)是q

Q，其讀寫頭正在掃描的字符是a

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

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

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

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

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

和a’=a。因為集合Q和

都是有限集合，

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

Q，子集F

中的狀態(tài)稱為終止狀態(tài)。第13章的有限狀態(tài)自動機是圖靈機的特殊情況。它不改變讀寫帶上的字符，沒有輸出值，停機在接收狀態(tài)表示接收輸入字符串。6圖靈機計算一個函數(shù)或識別一個字符串的過程開始時，輸入數(shù)據(jù)或字符串從左邊第一個方格開始放在讀寫帶上，圖靈機處在開始狀態(tài)q0，而讀寫頭指向第一個方格?！と缓?，根據(jù)轉(zhuǎn)換函數(shù)不斷地變更狀態(tài)、修改符號、和移動讀寫頭。當進入了一個終止狀態(tài)qf

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

，|

|=d，d

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

’與

不同，|’

|

2。我們可用

’中兩字符a和b(可視為0和1)來對

中每個字符編碼，長為k=

lgd

。這樣一來，對

中一個字符的操作變成了對一個長為k的序列的操作。因為d和k都是常數(shù)，圖靈機T’的漸近復(fù)雜度與T的相同。所以，除一進制的編碼外，用不同的符號集不影響算法的復(fù)雜度。為方便起見，以下討論中，我們就假定

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

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

k

k-1；endwhile；

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

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

E’ E’

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

thenE’

E’

{e} //把e放回來 endifendforreturn

G’End11判斷型問題的形式語言表示給定字符集

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

，稱為

的全語言，記為

*。例如，

={0,1}，

*={

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

，它的全語言的一個子集L

*稱為定義在

上的一個語言。換句話說，任何一個

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

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

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

的一個實例并且有答案yes；x代表問題

的一個實例并且有答案no；x不代表問題

的一個實例，而是一個雜亂的子符串。用

(x)=1表示

第1種情況，用

(x)=0表示

第2,3種情況。給定一個判斷型問題

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

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

L(

)={x|x

*and

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

的算法A所做的事就是對任何一個輸入字符串x

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

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

表示拒絕x，和不回答，

表示不能判定x。所以，解一個判斷型問題

的算法就等價于一個識別語言L(

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

L(

)。我們把這樣的算法稱為判斷型算法。為簡便起見，除非特別說明，本章討論的問題和算法都是指判斷型問題和算法。14定義14.4

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

y

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

給定一個問題

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

)正好等于被算法A所接收的語言，那么稱問題

或語言L(

)被A所接收。如果問題

對應(yīng)的語言L(

)正好等于被算法A所判定的語言，那么稱問題

或語言L(

)被A所判定。顯然，給定問題

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

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

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

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

給定兩個語言L1和L2，如果存在一個算法f，它把

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

L1

當且僅當f(x)

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

p

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

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

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

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

外的一個字符串映射到L2

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

1和

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

1)和L(

2)。如果語言L(

1)可多項式歸約到語言L(

2)，則稱問題

1可多項式歸約到問題

2，記為

1

p

2。從問題的角度看，

1

p

2意味著

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

2的一個實例f(x)并且

1(x)=yes

當且僅當

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

如果L1

p

L2，而語言L2可被一多項式算法A2所判定，那么必存在一個多項式算法A1使語言L1被A1所判定。證明：

如下圖(14-3)所示，我們可這樣設(shè)計A1:對任一個字符串x，A1先用多項式轉(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

當且僅當x

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

L2yes,x

L1no,x

L1no,f(x)

L2A1圖14-319注評：如果問題

1可多項式歸約到問題

2，那么從多項式可解的角度看，問題

2可認為比

1更難，因為找到

2的多項式算法就可以有

1的多項式算法。如果問題

2也可以多項式歸約到問題

1，那么我們認為兩者在多項式可解上等價。證明

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

t1

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

nc，這是因為在nc步時間內(nèi)，算法不可能產(chǎn)生多于nc個字符。

又因為算法A2是個多項式算法，所以t2<|f(x)|k

≤

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

20上一節(jié)把問題

對應(yīng)于

={0,1}上的一個語言L(

)。因此，對問題的分類也就是對語言的分類。P語言類定義14.8

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

*可被一多項式算法所判定}。如果

對應(yīng)的語言L(

)屬于P類，那么問題

也稱為P類問題。定理14.2

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

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

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

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

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

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

。在確定的圖靈機中，

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

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

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

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

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

L都可以被T在多項式時間內(nèi)接收，即存在一條計算路徑，其長度

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

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

|L

*并且L

可被一非確定的圖靈機在多項式時間內(nèi)接收}。

如果問題

對應(yīng)的語言L(

)屬于NP類，那么問題

稱為NP類問題。24定理14.3 P

NP。證明：因為一個確定的圖靈機可看作一個非確定的圖靈機的一個特例，只是它的轉(zhuǎn)換函數(shù)

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

NP。

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

L的。如果x

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

L，則一定有字符串y。字符串y稱為“證書”(certificate)。如果我們把x和y合起來看作輸入字符串的話，T就是一個確定的圖靈機。當這個檢驗機T對輸入字符串x和y進行運算后輸出T(x,y)=1，我們說T接收字符串(x,y)。25定義14.1一個語言L稱為一個多項式時間可檢驗的語言，如果存在一個(確定的)圖靈機T使得x

L

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

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

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

L

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

對應(yīng)的語言L(

)有NP-算法，那么

也就屬于NP類了，所以，在證明

是NP類問題時，我們只要設(shè)計一個多項式檢驗算法A去接受L(

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

(x)=yes，并給出多項式檢驗步驟即可。當

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

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

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

29簡單來講，NP完全(NPC)問題就是NP類中最難的問題。如果有一個NPC問題有多項式算法，那么所有NP類問題都會有多項式算法。定義14.12一個語言L被稱為NPC語言，如果它滿足：(1)L

NP;

(2)NP類中任何一個語言L’可多項式歸約到L，即L’

p

L。註評:如果一個語言L只滿足第2個條件，那么L被稱為一個NP難(NP-hard)語言。如果一個問題

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

)是NPC或NP難語言，那么問題

則對應(yīng)地被稱為是一個NPC問題或NP難問題。一個NPC問題顯然也是一個NP難問題。定義14.13

NPC語言類是所有NPC語言的集合，簡記為NPC。即: NPC={L|L

是一個NPC語言}。通常，NPC也用來代表所有NPC問題的集合3.NPC語言類和NPC問題

30定理14.4

任何一個NPC語言有多項式判定算法當且僅當P=NP。證明：如果某個NPC語言L有多項式算法來判定，那么L

P。又因為L

NPC，任何一個NP語言L’可以多項式歸約到L，即L’

p

L，由定理14.1，L’可以被一個多項式算法所判定，所以有L’

P。這就意味著NP

P，但由定理14.3，P

NP，所以得到P=NP。反之，如果有P=NP，那么因為NPC

NP=P，所以任何一個NPC語言L有多項式算法判定。

推論14.5

如果一個NPC語言L沒有多項式算法，那么P

NPC=

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

NPC

。那么必有一語言L’

P

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

NPC

NP=P。那么，L也必定有多項式算法，這與“L沒有多項式算法”矛盾。

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

NPC=

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

=((x1

x2)

((

x1

x3)

x4))

(

x2

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

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

=((x1

x2)

((

x1

x3)

x4))

(

x2

x3)=((0

0)

((

0

1)

1))

(

0

1)=(0

(1

1))

(1

1)=(0

1)

1=1。

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

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

=(x1

x2)

x1

x2

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

是NPC問題時，只需遵循下面的方法。新問題

是NPC問題的證明步驟:證明

NP選一個已被證明的NPC問題

’并證明

’

p

。正確性：因為

’

NPC，所以NP類中任一個問題

’’可多項式歸約到

’，即

’’

p

’。又因為

’

p

，所以

’’也可多項式歸約到

，

’’

p

，盡管這個歸約需要二步。

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

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

一個可滿足的電路實例x1x2x3(b)

一個不可滿足的電路實例定理14.6

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

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

可以多項式歸約到語言circuit-SAT。(接下頁)37定理14.6 的證明(繼續(xù)2)因為L

NP，則有多項式檢驗機T對字符串x和證書y進行識別判斷。設(shè)x=x1x2…xn，y=y1y2…ym，m

≤nc。x

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

到M)中初始放0。假設(shè)輸出符號t放在編號為n+m的格子中。因為T在M

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

使得檢驗機T在M

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

可被滿足。(A)

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

lgM

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

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

lgW

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

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

等于檢驗機T

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

等于檢驗機T

一步操作后新的地址。所以，每層的輸出變量的個數(shù)和含義與輸入變量相同，但數(shù)值不同。這一層的構(gòu)造是通用的，一共構(gòu)造M層。圖(14-6)顯示了第一層的構(gòu)造。見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

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

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

E計算檢驗機T的轉(zhuǎn)換函數(shù)

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

是輸出信號。

=1表示a’=

(a)，而

=0表示a’=a。

通過DEMUX電路到達原地址k的位置，與輸入信號

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

=1或

=0，輸出a’=

a或a’=

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

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

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

lgM

成正比。原地址減1，加1，或加0的計算需邏輯門和連線的個數(shù)也是O(r)。(接下頁)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信號Dv’1

v’2…v’r圖14-6

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

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

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

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

w2…wd

v1

v2…vru0

u1…un+mun+m+1

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

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

p

Circuit-SAT。

43若干著名NPC問題的證明這一節(jié)我們介紹若干個早期被證明的最著名的NPC問題。下圖(14-8)標出了我們要討論的NPC問題以及與之關(guān)聯(lián)的歸約樹。因為證明這些問題屬于NP類很容易，我們只證明多項式歸約部分。Circuit-SATSAT3-SATCliqueVertex-CoverHamilton-CycleTSPSubset-SumSet-Partitionk-Colorability44若干著名NPC問題的證明順序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)例因為為邏輯門i而構(gòu)造的表達式fi正確地定義了其輸出和輸入變量之間的關(guān)系，所以容易看出電路C可被滿足當且僅當

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

的時間顯然是門的個數(shù)和連線個數(shù)的多項式函數(shù)，所以有Circuit-SAT

p

SAT。472. SAT問題

p

3-SAT問題3-SAT是SAT的一個子問題，因為表達式

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

稱為3-CNF。例如:

=(x1

x1

x2)

(x3

x2

x4)

(

x1

x3

x4)。3-SAT問題是判斷一個給定的3-CNF的表達式

是否可滿足。下面，我們說明如何把SAT問題的一個實例多項式轉(zhuǎn)換為一個

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

=((x1

x2)

((

x1

x3)

x4))

(

x2

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

可以用一個二叉樹來表示，用一個新變量代表每個內(nèi)結(jié)點運算后的輸出變量。這一步可在多項式時間內(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) 為每個內(nèi)結(jié)點構(gòu)造一個布爾表達式來表示它的輸出變量和它的兩個輸入變量之間的關(guān)系。然后，把所有這些小表達式以及根結(jié)點的輸出變量用與的運算串連起來得到表達式

’

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

為

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

(y2

y3)為例說明。y1y2y3y1

(y2

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

y1

y2

y3)

(y1

y2

y3)

(y1

y2

y3)

(y1

y2

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

y1

y2

y3)

(y1

y2

y3)

(y1

y2

y3)

(y1

y2

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

y2

y3)

(

y1

y2

y3)

(

y1

y2

y3)

(

y1

y2

y3)。因為真值表中等于0的行最多是8個，所以這個3-CNF中的子句最多有8個，因此在線性時間里可以完成對

’中所有小表達式的變換，即把所有小表達式變換為等價的3-CNF表達式。把

’中每個小表達式換為等價的3-CNF表達式后得到的表達式

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

’’的構(gòu)造可在多項式時間內(nèi)完成。又因為

’’可被滿足當且僅當’可被滿足，而

’可被滿足當且僅當

可被滿足。因此有SAT問題

p

3-SAT問題。513. 3-SAT問題

p

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

=C1

C2…

Cm。子句Ci

(1

i

m)

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

k

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

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

x1

x2

x3C3=x1

x2

x3

x2x1C1=x1

x2

x3

x3

x1x2x3表達式：

=(x1

x2

x3)(

x1

x2

x3)(x1

x2

x3)x1

x2

x3構(gòu)造的圖接下頁53構(gòu)造k-clique問題實例的多項式算法(繼續(xù)2)(3)

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

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

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

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

p

Clique問題。55

56

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

57

585. vertex-Cover

p

Hamilton-Cycle假設(shè)vertex-cover的特例是圖G和k，多項式轉(zhuǎn)換算法構(gòu)造圖G’如下。第1步: 對應(yīng)于G中每一條邊(u,v)，構(gòu)造一個小圖Wuv，稱為小器具。下圖(14-14(a))顯示了這個構(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個點。其中有標記的4個點與圖中其他點相連。如果它被G’的一條哈密爾頓回路穿過的話，只能有三種可能。圖中(b)(c)(d)顯示了這三種可能的情況。59

uabc(a)

頂點u有3條邊(b)

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

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

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

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

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

串連一次，不同的是，Dv連的口子是(vu,2)和(vu,1)，而Du連的口子是(uv,2)和(uv,1)。這也就是說，u和v各自用Wuv不同一側(cè)的兩個口子。路徑Pu也許會在哈密爾頓回路中用到，也許不用。如果它是哈密爾頓回路中一部分，在它穿越每個小器具Wuv時，是經(jīng)過12個點還是6個點要看是否有另外一條路徑Pv穿過Wuv。下頁圖(14-16)顯示了一個有4個頂點和4條邊的圖G，以及為它所構(gòu)造的4個小器具和4條路徑。對應(yīng)頂點u的路徑的兩端用Pu和P’u標注。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個點，s1,s2,…,sk。然后將點si

(1

i

k)

與每一個Du

(u

G)的兩頭相連。下圖(14-17)顯示了，當k=2時，在圖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對應(yīng)于2-cover{u,b}的哈密爾頓回路假設(shè)G’中有一條哈密爾頓回路，從點s1開始。因為每個頂點正好出現(xiàn)一次，我們可假定頂點s1,s2,…,sk,

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

(1

i

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

pHamilton-Cycle。66Hamilton-cycle

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

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

V,E’

E。第2步，賦以當前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。這樣一來，G’(V’,E’)就是一個加權(quán)的完全圖。第4步，置k=n。轉(zhuǎn)換完成。(接下頁)67多項式轉(zhuǎn)換算法(繼續(xù))下圖(14-19)給出了一個構(gòu)造G’的例子。其中第3步中加的邊用粗線標出。dabcedabce(a)Hamilton-Cycle問題中的圖G(b)

TSP問題中的圖G’0000000111顯然，圖G有一條哈密爾頓回路當且僅當G’中有一條總長為0的貨郎擔回路。所以有Hamilton-Cycle

pTSP。687. 3-SAT

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

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

有2n+2m

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

(1

i

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

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

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

(j

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

(1

k

m)的那一位上，如果xi

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

xi

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

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

=(x1

x2

x3)

(

x1

x2

x3)

(x1

x2

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

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