《算法設(shè)計(jì)與分析》第10章課件

第10章NP完全問(wèn)題第10章NP完全問(wèn)題110.1基本概念

10.2Cook定理和證明

10.3一些典型的NP完全問(wèn)題10.1基本概念 210.1

基本概念

10.1

基本概念 3將能在多項(xiàng)式時(shí)間求解的問(wèn)題看作易處理問(wèn)題(tractableproblem)，而將至今尚未找到多項(xiàng)式時(shí)間算法求解的問(wèn)題視為難處理問(wèn)題(intractableproblem)。

將能在多項(xiàng)式時(shí)間求解的問(wèn)題看作易處理問(wèn)題(tractable410.1.1

不確定算法和不確定機(jī)為便于研究，先假定一種運(yùn)行不確定算法的抽象計(jì)算模型，該抽象機(jī)除了包含第2.1.3節(jié)的抽象機(jī)模型的基本運(yùn)算外，最根本的區(qū)別在于它新增了下面一個(gè)新函數(shù)和兩個(gè)新語(yǔ)句：（1）Choice(S)：任意選擇集合S的一個(gè)元素；

（2）Failure：發(fā)出不成功完成信號(hào)后算法終止；（3）Success：發(fā)出成功完成信號(hào)后算法終止。10.1.1不確定算法和不確定機(jī)為便于研究，先假定一5例10－1在n個(gè)元素的數(shù)組a中查找給定元素x，如果x在其中，則確定使a[j]==x的下標(biāo)j，否則輸出-1。

【程序10－1】不確定搜索算法voidSearch(inta[],Tx){intj=Choice(0,n-1); if(a[j]==x){cout<<j;Success(); }cout<<-1;Failure(); }例10－1在n個(gè)元素的數(shù)組a中查找給定元素x，如果x在其中6包含Choice函數(shù)的算法能按如下既定方式執(zhí)行：當(dāng)算法執(zhí)行中需作出一系列的Choice函數(shù)選擇時(shí)，當(dāng)且僅當(dāng)對(duì)于Choice的任何一組選擇都不會(huì)導(dǎo)致成功信號(hào)時(shí)，此算法在O(1)時(shí)間不成功終止；否則，只要存在一組選擇能夠?qū)е鲁晒r(shí)，算法總能采取該組選擇使得算法成功終止。包含不確定選擇語(yǔ)句，并能按上述方式執(zhí)行一個(gè)算法的機(jī)器稱(chēng)為不確定機(jī)（nondeterministicmachine）。在不確定機(jī)上執(zhí)行的算法稱(chēng)為不確定算法（nondeterministicalgorithm）。

包含Choice函數(shù)的算法能按如下既定方式執(zhí)行：當(dāng)算法執(zhí)行中7例10-2

將n個(gè)元素的序列排成有序序列。【程序10-2】

不確定排序算法voidNSort(inta[],intn){intb[mSize],i,j;for(i=0;i<n;i++)b[i]=0; for(i=0;i<n;i++){ j=Choice(0,n-1); if(b[j])Failure(); b[j]=a[i]; }

例10-2將n個(gè)元素的序列排成有序序列。8for(i=0;i<n-1;i++) if(b[i]>b[i+1])Failure(); for(i=0;i<n;i++)cout<<b[i]<<'';cout<<endl;Success(); }for(i=0;i<n-1;i++) 9定義10-1

（不確定算法時(shí)間復(fù)雜度）一個(gè)不確定算法所需的時(shí)間是指對(duì)任意一個(gè)輸入，當(dāng)存在一個(gè)選擇序列導(dǎo)致成功完成時(shí)，達(dá)到成功完成所需的最少程序步。在不可能成功完成的情況下，所需時(shí)間總是O(1)。

定義10-1（不確定算法時(shí)間復(fù)雜度）一個(gè)不確定算法所需的時(shí)10例10-3

（最大集團(tuán)及其判定問(wèn)題）無(wú)向圖G=(V,E)的一個(gè)完全子圖稱(chēng)為該圖的一個(gè)集團(tuán)（clique）。集團(tuán)的規(guī)模用集團(tuán)的頂點(diǎn)數(shù)衡量。最大集團(tuán)問(wèn)題是確定圖G的最大集團(tuán)規(guī)模的問(wèn)題。最大集團(tuán)判定問(wèn)題（G,k）是對(duì)給定正整數(shù)k，判定圖G是否存在一個(gè)規(guī)模至少為k的集團(tuán)。例10-3（最大集團(tuán)及其判定問(wèn)題）無(wú)向圖G=(V,E)的11【程序10-3】

最大集團(tuán)判定問(wèn)題不確定算法voidClique（intg[][mSize],intn,intk）{ S=; for(inti=0;i<k;i++){ intt=Choice(0,n-1); if(tS)Failure(); S=S∪{t}; } for(對(duì)所有(i,j)，iS，jS且ij) if((i,j)E)Failure(); Success();}【程序10-3】最大集團(tuán)判定問(wèn)題不確定算法1210.1.2可滿(mǎn)足性問(wèn)題例10-4

可滿(mǎn)足性問(wèn)題（satisfiabilityproblem）是一個(gè)判定問(wèn)題，它確定對(duì)于一個(gè)給定的命題公式，是否存在布爾變量的一種賦值（也稱(chēng)真值指派）使該公式為真。CNF可滿(mǎn)足性是指判定一個(gè)CNF公式的可滿(mǎn)足性。10.1.2可滿(mǎn)足性問(wèn)題例10-4可滿(mǎn)足性問(wèn)題（sa13【程序10-4】可滿(mǎn)足性問(wèn)題的不確定算法voidEval(CNFE,intn){ intx[mSize]; for(inti=1;i<=n;i++) x[i]=Choice(0,1); if(E(x,n))Success(); elseFailure();}【程序10-4】可滿(mǎn)足性問(wèn)題的不確定算法1410.1.3

P類(lèi)和NP類(lèi)問(wèn)題定義10-2

（P類(lèi)和NP類(lèi)）P是所有可在多項(xiàng)式時(shí)間內(nèi)用確定算法求解的判定問(wèn)題的集合。NP是所有可在多項(xiàng)式時(shí)間內(nèi)用不確定算法求解的判定問(wèn)題的集合。定義10-3

（多項(xiàng)式約化）令Q1和Q2是兩個(gè)問(wèn)題，如果存在一個(gè)確定算法A求解Q1，而算法A以多項(xiàng)式時(shí)間調(diào)用另一個(gè)求解Q2的確定算法B。若不計(jì)B的工作量，算法A是多項(xiàng)式時(shí)間的，則稱(chēng)Q1約化（reducedto）為Q2，記做Q1∝Q2。10.1.3

P類(lèi)和NP類(lèi)問(wèn)題定義10-2（P類(lèi)和NP15性質(zhì)10-1

若Q1P，Q2∝Q1，則有Q2P。性質(zhì)10-2若Q1∝Q2，Q2∝Q3，則Q1∝Q3。性質(zhì)10-1若Q1P，Q2∝Q1，則有Q2P。1610.1.4NP難度和NP完全問(wèn)題定義10-4

（NP難度）對(duì)于問(wèn)題Q以及任意問(wèn)題Q1NP，都有Q1∝Q，則稱(chēng)Q是NP難度（NPhard）的。定義10-5

（NP完全）對(duì)于問(wèn)題QNP，Q是NP難度的，則稱(chēng)Q是NP完全（NPcomplete）的。10.1.4NP難度和NP完全問(wèn)題定義10-4（NP難17如何確定某個(gè)問(wèn)題Q是否是NP難度的？一般的證明策略由以下兩步組成：（1）選擇一個(gè)已經(jīng)證明是NP難度問(wèn)題Q1；（2）求證Q1∝Q。由于Q1是NP難度的，因此所有NP類(lèi)問(wèn)題都可約化到Q1，根據(jù)約化的傳遞性，任何NP類(lèi)問(wèn)題都可約化到Q，所以Q是NP難度的。如果進(jìn)一步表明Q本身是NP類(lèi)的，則問(wèn)題Q是NP完全的。如何確定某個(gè)問(wèn)題Q是否是NP難度的？一般的證明策略由以下兩步1810.2Cook定理和證明10.2Cook定理和證明1910.2.1Cook定理斯蒂芬·庫(kù)克（StevenCook）于1971年證明了第一個(gè)NP完全問(wèn)題，稱(chēng)為Cook定理。Cook定理表明可滿(mǎn)足性問(wèn)題是NP完全的。CNF可滿(mǎn)足性問(wèn)題也被證明是NP完全的。自從Cook證明了可滿(mǎn)足性問(wèn)題是NP完全的之后，迄今為止至少有300多個(gè)問(wèn)題被證明是NP難度問(wèn)題，但尚未證明其中任何一個(gè)是屬于P的。定理10-1

（Cook定理）可滿(mǎn)足性問(wèn)題在P中，當(dāng)且僅當(dāng)P=NP。定理10-2CNF可滿(mǎn)足性問(wèn)題是NP完全的。10.2.1Cook定理斯蒂芬·庫(kù)克（StevenC2010.3一些典型的NP完全問(wèn)題

10.3一些典型的NP完全問(wèn)題21證明一個(gè)問(wèn)題Q是NP難度（或NP完全）問(wèn)題的具體步驟如下：（1）選擇一個(gè)已知其具有NP難度的問(wèn)題Q1；（2）證明能夠從Q1的一個(gè)實(shí)例I1，在多項(xiàng)式時(shí)間內(nèi)構(gòu)造Q的一個(gè)實(shí)例I；（3）證明能夠在多項(xiàng)式時(shí)間內(nèi)從I的解確定I1的解。（4）從（2）和（3）可知，Q1∝Q；（5）由（1）和（4）及約化的傳遞性得出所有NP類(lèi)問(wèn)題均可約化到Q，所以Q是NP難度的；（6）如果Q是NP類(lèi)問(wèn)題，則Q是NP完全的。證明一個(gè)問(wèn)題Q是NP難度（或NP完全）問(wèn)題的具體步驟如下：2210.3.1

最大集團(tuán)定理10-3

CNF可滿(mǎn)足性∝最大集團(tuán)判定問(wèn)題。證明分兩步證明這一定理：首先尋找一種方法，它能在多項(xiàng)式時(shí)間內(nèi)，從任意給定的CNF公式F構(gòu)造一個(gè)無(wú)向圖G=(V,E)；然后證明，F(xiàn)是可滿(mǎn)足的，當(dāng)且僅當(dāng)G有一個(gè)規(guī)模至少為k的集團(tuán)。10.3.1

最大集團(tuán)定理10-3CNF可滿(mǎn)足性∝最大集23第一步：以任意給定的CNF公式F為輸入，構(gòu)造一個(gè)相應(yīng)的無(wú)向圖G，并且這種構(gòu)造能夠在多項(xiàng)式時(shí)間內(nèi)完成。令是一個(gè)CNF形式的命題公式，xi，1in，是F中的變量。由F生成一個(gè)無(wú)向圖G=(V,E)的方法為：V={<,i>|是子句Ci的一個(gè)文字}，E={(<,i>,<,j>)|ij且

}。

第一步：以任意給定的CNF公式F為輸入，構(gòu)造一個(gè)相應(yīng)的無(wú)向圖24

可滿(mǎn)足性問(wèn)題實(shí)例F：

最大集團(tuán)實(shí)例G=(V,E):V={<,i>|是子句Ci的一個(gè)文字}，E={(<,i>,<,j>)|ij且}可滿(mǎn)足性問(wèn)題實(shí)例F：最大集團(tuán)實(shí)例G=(V,E):25第二步：如果能夠證明F可滿(mǎn)足，當(dāng)且僅當(dāng)G有一個(gè)規(guī)模至少為k的集團(tuán)，那么，便證明了CNF可滿(mǎn)足性問(wèn)題可以約化到最大集團(tuán)判定問(wèn)題。分兩方面證明此結(jié)論:一方面，若F是可滿(mǎn)足的，則必定存在對(duì)n個(gè)布爾變量的一種賦值，使得每個(gè)子句Ci中至少有一個(gè)文字為真。

另一方面，若G有一個(gè)規(guī)模至少為k的集團(tuán)G’＝（S，E’），設(shè)S={<1,1>,<2,2>,,<k,k>}是集團(tuán)的頂點(diǎn)集合，則必有i，ij，若不然，則頂點(diǎn)<i，i>和<j，j>之間沒(méi)有邊，S不是集團(tuán)。

第二步：如果能夠證明F可滿(mǎn)足，當(dāng)且僅當(dāng)G有一個(gè)規(guī)模至少為k26例10-5

設(shè)有命題公式F，圖G(V.E)有大小為2的集團(tuán)，F(xiàn)是可滿(mǎn)足的（可令x1＝true，x2＝false）例10-5設(shè)有命題公式F，圖G(V.E)有大小為22710.3.2頂點(diǎn)覆蓋例10－6

（頂點(diǎn)覆蓋判定問(wèn)題）對(duì)于無(wú)向圖G＝(V,E)，集合SV，如果E中所有邊都至少有一個(gè)頂點(diǎn)在S中，則稱(chēng)S是圖G的一個(gè)頂點(diǎn)覆蓋。覆蓋的規(guī)模是S中頂點(diǎn)的數(shù)目|S|。頂點(diǎn)覆蓋（vertexcover）問(wèn)題是指求圖G的最小規(guī)模的頂點(diǎn)覆蓋，而頂點(diǎn)覆蓋判定問(wèn)題是確定圖G是否存在規(guī)模至多為k的頂點(diǎn)覆蓋。10.3.2頂點(diǎn)覆蓋例10－6（頂點(diǎn)覆蓋判定問(wèn)題）對(duì)于28對(duì)于圖中所示的無(wú)向圖G，S1={1，3}和S2={0，2，4}分別是圖G的頂點(diǎn)覆蓋，S1是最小覆蓋，其規(guī)模為2。對(duì)于圖中所示的無(wú)向圖G，S1={1，3}和S2={0，2，429定理10－4

最大集團(tuán)判定問(wèn)題∝頂點(diǎn)覆蓋判定問(wèn)題。證明：分兩步證明這一結(jié)論。第一步：以最大集團(tuán)判定問(wèn)題的任一實(shí)例(G，k)，G=(V，E)，k為正整數(shù)，來(lái)構(gòu)造一個(gè)頂點(diǎn)覆蓋判定問(wèn)題的實(shí)例(G’，n-k)，G’=(V，)，n=|V|，={(u,v)|uV,vV且（u,v）E}。定理10－4最大集團(tuán)判定問(wèn)題∝頂點(diǎn)覆蓋判定問(wèn)題。30第二步：分兩方面證明“圖G有一個(gè)規(guī)模至少為k的集團(tuán)，當(dāng)且僅當(dāng)圖G’有一個(gè)規(guī)模至多為nk的結(jié)點(diǎn)覆蓋?！币环矫?，先證明：若圖G有一個(gè)規(guī)模至少為k的集團(tuán)S，則圖G’有一個(gè)規(guī)模至多為nk的結(jié)點(diǎn)覆蓋S’，S’＝VS。反證法：若G’不能被S’中的頂點(diǎn)所覆蓋，則必定存在邊(u,v)，頂點(diǎn)u和v均不在S’中，而在S中。這與S是圖G的一個(gè)集團(tuán)相矛盾。所以，S’必定是圖G’的頂點(diǎn)覆蓋。并且若|S|k，則|S’|nk。第二步：分兩方面證明“圖G有一個(gè)規(guī)模至少為k的集團(tuán)，當(dāng)且僅當(dāng)31另一方面，需證明：若G’有一個(gè)規(guī)模至多為nk的結(jié)點(diǎn)覆蓋S’，則G有一個(gè)規(guī)模至少為k的集團(tuán)S，S=VS’。反證法：若S不是完全圖，則S中至少有一對(duì)頂點(diǎn)uS，vS之間缺少邊，該邊（u,v）應(yīng)屬于，即S’未覆蓋此邊。這與S’是G’的頂點(diǎn)覆蓋相矛盾。因此，S必為完全圖。若|S’|nk，則|S|k。另一方面，需證明：若G’有一個(gè)規(guī)模至多為nk的結(jié)點(diǎn)覆蓋S’3210.3.3

3元CNF可滿(mǎn)足性

例10－7（3SAT）3元CNF可滿(mǎn)足性問(wèn)題是指一個(gè)CNF公式F中，每個(gè)子句包含恰好3個(gè)文字時(shí)的可滿(mǎn)足性問(wèn)題。10.3.3

3元CNF可滿(mǎn)足性例10－7（3SAT）33

可滿(mǎn)足性的若干結(jié)果是可滿(mǎn)足的，當(dāng)且僅當(dāng)公式f=(∨y1∨y2)∧(∨∨y2)∧(∨y1∨)∧(∨∨)是可滿(mǎn)足的。其中，是公式，y1和y2是變量。由于y1，y2，y1∨y2，∨y2,y1∨和∨不同時(shí)為真。所以，是可滿(mǎn)足的，當(dāng)且僅當(dāng)公式f是可滿(mǎn)足的。可滿(mǎn)足性的若干結(jié)果341∨2是可滿(mǎn)足的，當(dāng)且僅當(dāng)公式f=(1∨2∨y)∧(1∨2∨)是可滿(mǎn)足的。由于y，兩者之一為假。所以，1∨2是可滿(mǎn)足的，當(dāng)且僅當(dāng)公式f是可滿(mǎn)足的。1∨2是可滿(mǎn)足的，當(dāng)且僅當(dāng)公式35f1∨f2是可滿(mǎn)足的，當(dāng)且僅當(dāng)公式f=(f1∨y)∧(f2∨)是可滿(mǎn)足的，f1和f2是公式，y是變量，并且不出現(xiàn)在f1和f2中。若f1∨f2是可滿(mǎn)足的，則必有f1或f2為真。若f1為真，可令y為假，則f可滿(mǎn)足；否則，若f2為真，可令y為真，則f可滿(mǎn)足。若f是可滿(mǎn)足的，因?yàn)閥，若y為真，則必有f2為真，若y為假，則必有f1為真。即無(wú)論y為何值，只有f1∨f2為真時(shí)，f才為真。f1∨f2是可滿(mǎn)足的，當(dāng)且僅當(dāng)公式36定理10－5CNF可滿(mǎn)足性∝3元CNF可滿(mǎn)足性。證明：使用上述結(jié)論，可將任意一個(gè)CNF公式在多項(xiàng)式時(shí)間內(nèi)轉(zhuǎn)換成一個(gè)3元CNF公式，且這種轉(zhuǎn)換能夠維持可滿(mǎn)足性不變。因此，CNF可滿(mǎn)足性∝3元CNF可滿(mǎn)足性，故3元CNF可滿(mǎn)足性問(wèn)題是NP完全的。定理10－5CNF可滿(mǎn)足性∝3元CNF可滿(mǎn)足性。3710.3.4

圖的著色數(shù)例10－8

（圖著色數(shù)判定問(wèn)題）對(duì)給定的無(wú)向圖G著色，是指對(duì)圖中任何兩個(gè)相鄰頂點(diǎn)都分配不同顏色。圖的著色問(wèn)題是求對(duì)給定無(wú)向圖著色所必需的最少顏色種類(lèi)，而圖著色判定問(wèn)題是確定能否使用k種顏色對(duì)一個(gè)給定的無(wú)向圖著色的問(wèn)題。10.3.4圖的著色數(shù)例10－8（圖著色數(shù)判定問(wèn)題）對(duì)給38

定理10－63元CNF可滿(mǎn)足性∝著色數(shù)判定問(wèn)題。證明：仍然分兩步證明這一結(jié)論。第一步：以3元CNF可滿(mǎn)足性問(wèn)題的任意一個(gè)實(shí)例公式F為輸入，構(gòu)造一個(gè)著色數(shù)判定問(wèn)題的實(shí)例(G，k)，其中G=(V,E)為無(wú)向圖，k為正整數(shù)。第二步：從兩方面證明“3元CNF公式F是可滿(mǎn)足的，當(dāng)且僅當(dāng)圖G是n+1可著色的?！?/p>

定理10－63元CNF可滿(mǎn)足性∝著色數(shù)判定問(wèn)題。39總共3n+k個(gè)頂點(diǎn)

總共3n+k個(gè)頂點(diǎn)40《算法設(shè)計(jì)與分析》第10章課件41證明：3元CNF公式F是可滿(mǎn)足的，當(dāng)且僅當(dāng)圖G是n+1可著色的。若F是可滿(mǎn)足的，則圖G是n+1可著色的若圖G是n+1可著色的，則F是可滿(mǎn)足的證明：3元CNF公式F是可滿(mǎn)足的，當(dāng)且僅當(dāng)圖G是n+1可著色42綜上所述，可在多項(xiàng)式時(shí)間內(nèi)從3元CNF可滿(mǎn)足性問(wèn)題的任意一個(gè)實(shí)例公式F，構(gòu)造一個(gè)圖著色數(shù)問(wèn)題的實(shí)例無(wú)向圖G=(V,E)，并且3元CNF公式F是可滿(mǎn)足的，當(dāng)且僅當(dāng)圖G是n+1可著色的，所以，3元CNF可滿(mǎn)足性∝著色數(shù)判定問(wèn)題，著色數(shù)判定問(wèn)題是NP完全的。綜上所述，可在多項(xiàng)式時(shí)間內(nèi)從3元CNF可滿(mǎn)足性問(wèn)題的任意一個(gè)43第10章NP完全問(wèn)題第10章NP完全問(wèn)題4410.1基本概念

10.2Cook定理和證明

10.3一些典型的NP完全問(wèn)題10.1基本概念 4510.1

基本概念

10.1

基本概念 46將能在多項(xiàng)式時(shí)間求解的問(wèn)題看作易處理問(wèn)題(tractableproblem)，而將至今尚未找到多項(xiàng)式時(shí)間算法求解的問(wèn)題視為難處理問(wèn)題(intractableproblem)。

將能在多項(xiàng)式時(shí)間求解的問(wèn)題看作易處理問(wèn)題(tractable4710.1.1

不確定算法和不確定機(jī)為便于研究，先假定一種運(yùn)行不確定算法的抽象計(jì)算模型，該抽象機(jī)除了包含第2.1.3節(jié)的抽象機(jī)模型的基本運(yùn)算外，最根本的區(qū)別在于它新增了下面一個(gè)新函數(shù)和兩個(gè)新語(yǔ)句：（1）Choice(S)：任意選擇集合S的一個(gè)元素；

（2）Failure：發(fā)出不成功完成信號(hào)后算法終止；（3）Success：發(fā)出成功完成信號(hào)后算法終止。10.1.1不確定算法和不確定機(jī)為便于研究，先假定一48例10－1在n個(gè)元素的數(shù)組a中查找給定元素x，如果x在其中，則確定使a[j]==x的下標(biāo)j，否則輸出-1。

【程序10－1】不確定搜索算法voidSearch(inta[],Tx){intj=Choice(0,n-1); if(a[j]==x){cout<<j;Success(); }cout<<-1;Failure(); }例10－1在n個(gè)元素的數(shù)組a中查找給定元素x，如果x在其中49包含Choice函數(shù)的算法能按如下既定方式執(zhí)行：當(dāng)算法執(zhí)行中需作出一系列的Choice函數(shù)選擇時(shí)，當(dāng)且僅當(dāng)對(duì)于Choice的任何一組選擇都不會(huì)導(dǎo)致成功信號(hào)時(shí)，此算法在O(1)時(shí)間不成功終止；否則，只要存在一組選擇能夠?qū)е鲁晒r(shí)，算法總能采取該組選擇使得算法成功終止。包含不確定選擇語(yǔ)句，并能按上述方式執(zhí)行一個(gè)算法的機(jī)器稱(chēng)為不確定機(jī)（nondeterministicmachine）。在不確定機(jī)上執(zhí)行的算法稱(chēng)為不確定算法（nondeterministicalgorithm）。

包含Choice函數(shù)的算法能按如下既定方式執(zhí)行：當(dāng)算法執(zhí)行中50例10-2

將n個(gè)元素的序列排成有序序列。【程序10-2】

不確定排序算法voidNSort(inta[],intn){intb[mSize],i,j;for(i=0;i<n;i++)b[i]=0; for(i=0;i<n;i++){ j=Choice(0,n-1); if(b[j])Failure(); b[j]=a[i]; }

例10-2將n個(gè)元素的序列排成有序序列。51for(i=0;i<n-1;i++) if(b[i]>b[i+1])Failure(); for(i=0;i<n;i++)cout<<b[i]<<'';cout<<endl;Success(); }for(i=0;i<n-1;i++) 52定義10-1

（不確定算法時(shí)間復(fù)雜度）一個(gè)不確定算法所需的時(shí)間是指對(duì)任意一個(gè)輸入，當(dāng)存在一個(gè)選擇序列導(dǎo)致成功完成時(shí)，達(dá)到成功完成所需的最少程序步。在不可能成功完成的情況下，所需時(shí)間總是O(1)。

定義10-1（不確定算法時(shí)間復(fù)雜度）一個(gè)不確定算法所需的時(shí)53例10-3

（最大集團(tuán)及其判定問(wèn)題）無(wú)向圖G=(V,E)的一個(gè)完全子圖稱(chēng)為該圖的一個(gè)集團(tuán)（clique）。集團(tuán)的規(guī)模用集團(tuán)的頂點(diǎn)數(shù)衡量。最大集團(tuán)問(wèn)題是確定圖G的最大集團(tuán)規(guī)模的問(wèn)題。最大集團(tuán)判定問(wèn)題（G,k）是對(duì)給定正整數(shù)k，判定圖G是否存在一個(gè)規(guī)模至少為k的集團(tuán)。例10-3（最大集團(tuán)及其判定問(wèn)題）無(wú)向圖G=(V,E)的54【程序10-3】

最大集團(tuán)判定問(wèn)題不確定算法voidClique（intg[][mSize],intn,intk）{ S=; for(inti=0;i<k;i++){ intt=Choice(0,n-1); if(tS)Failure(); S=S∪{t}; } for(對(duì)所有(i,j)，iS，jS且ij) if((i,j)E)Failure(); Success();}【程序10-3】最大集團(tuán)判定問(wèn)題不確定算法5510.1.2可滿(mǎn)足性問(wèn)題例10-4

可滿(mǎn)足性問(wèn)題（satisfiabilityproblem）是一個(gè)判定問(wèn)題，它確定對(duì)于一個(gè)給定的命題公式，是否存在布爾變量的一種賦值（也稱(chēng)真值指派）使該公式為真。CNF可滿(mǎn)足性是指判定一個(gè)CNF公式的可滿(mǎn)足性。10.1.2可滿(mǎn)足性問(wèn)題例10-4可滿(mǎn)足性問(wèn)題（sa56【程序10-4】可滿(mǎn)足性問(wèn)題的不確定算法voidEval(CNFE,intn){ intx[mSize]; for(inti=1;i<=n;i++) x[i]=Choice(0,1); if(E(x,n))Success(); elseFailure();}【程序10-4】可滿(mǎn)足性問(wèn)題的不確定算法5710.1.3

P類(lèi)和NP類(lèi)問(wèn)題定義10-2

（P類(lèi)和NP類(lèi)）P是所有可在多項(xiàng)式時(shí)間內(nèi)用確定算法求解的判定問(wèn)題的集合。NP是所有可在多項(xiàng)式時(shí)間內(nèi)用不確定算法求解的判定問(wèn)題的集合。定義10-3

（多項(xiàng)式約化）令Q1和Q2是兩個(gè)問(wèn)題，如果存在一個(gè)確定算法A求解Q1，而算法A以多項(xiàng)式時(shí)間調(diào)用另一個(gè)求解Q2的確定算法B。若不計(jì)B的工作量，算法A是多項(xiàng)式時(shí)間的，則稱(chēng)Q1約化（reducedto）為Q2，記做Q1∝Q2。10.1.3

P類(lèi)和NP類(lèi)問(wèn)題定義10-2（P類(lèi)和NP58性質(zhì)10-1

若Q1P，Q2∝Q1，則有Q2P。性質(zhì)10-2若Q1∝Q2，Q2∝Q3，則Q1∝Q3。性質(zhì)10-1若Q1P，Q2∝Q1，則有Q2P。5910.1.4NP難度和NP完全問(wèn)題定義10-4

（NP難度）對(duì)于問(wèn)題Q以及任意問(wèn)題Q1NP，都有Q1∝Q，則稱(chēng)Q是NP難度（NPhard）的。定義10-5

（NP完全）對(duì)于問(wèn)題QNP，Q是NP難度的，則稱(chēng)Q是NP完全（NPcomplete）的。10.1.4NP難度和NP完全問(wèn)題定義10-4（NP難60如何確定某個(gè)問(wèn)題Q是否是NP難度的？一般的證明策略由以下兩步組成：（1）選擇一個(gè)已經(jīng)證明是NP難度問(wèn)題Q1；（2）求證Q1∝Q。由于Q1是NP難度的，因此所有NP類(lèi)問(wèn)題都可約化到Q1，根據(jù)約化的傳遞性，任何NP類(lèi)問(wèn)題都可約化到Q，所以Q是NP難度的。如果進(jìn)一步表明Q本身是NP類(lèi)的，則問(wèn)題Q是NP完全的。如何確定某個(gè)問(wèn)題Q是否是NP難度的？一般的證明策略由以下兩步6110.2Cook定理和證明10.2Cook定理和證明6210.2.1Cook定理斯蒂芬·庫(kù)克（StevenCook）于1971年證明了第一個(gè)NP完全問(wèn)題，稱(chēng)為Cook定理。Cook定理表明可滿(mǎn)足性問(wèn)題是NP完全的。CNF可滿(mǎn)足性問(wèn)題也被證明是NP完全的。自從Cook證明了可滿(mǎn)足性問(wèn)題是NP完全的之后，迄今為止至少有300多個(gè)問(wèn)題被證明是NP難度問(wèn)題，但尚未證明其中任何一個(gè)是屬于P的。定理10-1

（Cook定理）可滿(mǎn)足性問(wèn)題在P中，當(dāng)且僅當(dāng)P=NP。定理10-2CNF可滿(mǎn)足性問(wèn)題是NP完全的。10.2.1Cook定理斯蒂芬·庫(kù)克（StevenC6310.3一些典型的NP完全問(wèn)題

10.3一些典型的NP完全問(wèn)題64證明一個(gè)問(wèn)題Q是NP難度（或NP完全）問(wèn)題的具體步驟如下：（1）選擇一個(gè)已知其具有NP難度的問(wèn)題Q1；（2）證明能夠從Q1的一個(gè)實(shí)例I1，在多項(xiàng)式時(shí)間內(nèi)構(gòu)造Q的一個(gè)實(shí)例I；（3）證明能夠在多項(xiàng)式時(shí)間內(nèi)從I的解確定I1的解。（4）從（2）和（3）可知，Q1∝Q；（5）由（1）和（4）及約化的傳遞性得出所有NP類(lèi)問(wèn)題均可約化到Q，所以Q是NP難度的；（6）如果Q是NP類(lèi)問(wèn)題，則Q是NP完全的。證明一個(gè)問(wèn)題Q是NP難度（或NP完全）問(wèn)題的具體步驟如下：6510.3.1

最大集團(tuán)定理10-3

CNF可滿(mǎn)足性∝最大集團(tuán)判定問(wèn)題。證明分兩步證明這一定理：首先尋找一種方法，它能在多項(xiàng)式時(shí)間內(nèi)，從任意給定的CNF公式F構(gòu)造一個(gè)無(wú)向圖G=(V,E)；然后證明，F(xiàn)是可滿(mǎn)足的，當(dāng)且僅當(dāng)G有一個(gè)規(guī)模至少為k的集團(tuán)。10.3.1

最大集團(tuán)定理10-3CNF可滿(mǎn)足性∝最大集66第一步：以任意給定的CNF公式F為輸入，構(gòu)造一個(gè)相應(yīng)的無(wú)向圖G，并且這種構(gòu)造能夠在多項(xiàng)式時(shí)間內(nèi)完成。令是一個(gè)CNF形式的命題公式，xi，1in，是F中的變量。由F生成一個(gè)無(wú)向圖G=(V,E)的方法為：V={<,i>|是子句Ci的一個(gè)文字}，E={(<,i>,<,j>)|ij且

}。

第一步：以任意給定的CNF公式F為輸入，構(gòu)造一個(gè)相應(yīng)的無(wú)向圖67

可滿(mǎn)足性問(wèn)題實(shí)例F：

最大集團(tuán)實(shí)例G=(V,E):V={<,i>|是子句Ci的一個(gè)文字}，E={(<,i>,<,j>)|ij且}可滿(mǎn)足性問(wèn)題實(shí)例F：最大集團(tuán)實(shí)例G=(V,E):68第二步：如果能夠證明F可滿(mǎn)足，當(dāng)且僅當(dāng)G有一個(gè)規(guī)模至少為k的集團(tuán)，那么，便證明了CNF可滿(mǎn)足性問(wèn)題可以約化到最大集團(tuán)判定問(wèn)題。分兩方面證明此結(jié)論:一方面，若F是可滿(mǎn)足的，則必定存在對(duì)n個(gè)布爾變量的一種賦值，使得每個(gè)子句Ci中至少有一個(gè)文字為真。

另一方面，若G有一個(gè)規(guī)模至少為k的集團(tuán)G’＝（S，E’），設(shè)S={<1,1>,<2,2>,,<k,k>}是集團(tuán)的頂點(diǎn)集合，則必有i，ij，若不然，則頂點(diǎn)<i，i>和<j，j>之間沒(méi)有邊，S不是集團(tuán)。

第二步：如果能夠證明F可滿(mǎn)足，當(dāng)且僅當(dāng)G有一個(gè)規(guī)模至少為k69例10-5

設(shè)有命題公式F，圖G(V.E)有大小為2的集團(tuán)，F(xiàn)是可滿(mǎn)足的（可令x1＝true，x2＝false）例10-5設(shè)有命題公式F，圖G(V.E)有大小為27010.3.2頂點(diǎn)覆蓋例10－6

（頂點(diǎn)覆蓋判定問(wèn)題）對(duì)于無(wú)向圖G＝(V,E)，集合SV，如果E中所有邊都至少有一個(gè)頂點(diǎn)在S中，則稱(chēng)S是圖G的一個(gè)頂點(diǎn)覆蓋。覆蓋的規(guī)模是S中頂點(diǎn)的數(shù)目|S|。頂點(diǎn)覆蓋（vertexcover）問(wèn)題是指求圖G的最小規(guī)模的頂點(diǎn)覆蓋，而頂點(diǎn)覆蓋判定問(wèn)題是確定圖G是否存在規(guī)模至多為k的頂點(diǎn)覆蓋。10.3.2頂點(diǎn)覆蓋例10－6（頂點(diǎn)覆蓋判定問(wèn)題）對(duì)于71對(duì)于圖中所示的無(wú)向圖G，S1={1，3}和S2={0，2，4}分別是圖G的頂點(diǎn)覆蓋，S1是最小覆蓋，其規(guī)模為2。對(duì)于圖中所示的無(wú)向圖G，S1={1，3}和S2={0，2，472定理10－4

最大集團(tuán)判定問(wèn)題∝頂點(diǎn)覆蓋判定問(wèn)題。證明：分兩步證明這一結(jié)論。第一步：以最大集團(tuán)判定問(wèn)題的任一實(shí)例(G，k)，G=(V，E)，k為正整數(shù)，來(lái)構(gòu)造一個(gè)頂點(diǎn)覆蓋判定問(wèn)題的實(shí)例(G’，n-k)，G’=(V，)，n=|V|，={(u,v)|uV,vV且（u,v）E}。定理10－4最大集團(tuán)判定問(wèn)題∝頂點(diǎn)覆蓋判定問(wèn)題。73第二步：分兩方面證明“圖G有一個(gè)規(guī)模至少為k的集團(tuán)，當(dāng)且僅當(dāng)圖G’有一個(gè)規(guī)模至多為nk的結(jié)點(diǎn)覆蓋?！币环矫妫茸C明：若圖G有一個(gè)規(guī)模至少為k的集團(tuán)S，則圖G’有一個(gè)規(guī)模至多為nk的結(jié)點(diǎn)覆蓋S’，S’＝VS。反證法：若G’不能被S’中的頂點(diǎn)所覆蓋，則必定存在邊(u,v)，頂點(diǎn)u和v均不在S’中，而在S中。這與S是圖G的一個(gè)集團(tuán)相矛盾。所以，S’必定是圖G’的頂點(diǎn)覆蓋。并且若|S|k，則|S’|nk。第二步：分兩方面證明“圖G有一個(gè)規(guī)模至少為k的集團(tuán)，當(dāng)且僅當(dāng)74另一方面，需證明：若G’有一個(gè)規(guī)模至多為nk的結(jié)點(diǎn)覆蓋S’，則G有一個(gè)規(guī)模至少為k的集團(tuán)S，S=VS’。反證法：若S不是完全圖，則S中至少有一對(duì)頂點(diǎn)uS，vS之間缺少邊，該邊（u,v）應(yīng)屬于，即S’未覆蓋此邊。這與S’是G’的頂點(diǎn)覆蓋相矛盾。因此，S必為完全圖。若|S’|nk，則|S|k。另一方面，需證明：若G’有一個(gè)規(guī)模至多為nk的結(jié)點(diǎn)覆蓋S’7510.3.3

3元CNF可滿(mǎn)足性

例10－7（3SAT）3元CNF可滿(mǎn)足性問(wèn)題是指一個(gè)CNF公式F中，每個(gè)子句包含恰好3個(gè)文字時(shí)的可滿(mǎn)足性問(wèn)題。10.3.3

3元CNF可滿(mǎn)足性例10－7（3SAT）76

可滿(mǎn)足性的若干結(jié)果是可滿(mǎn)足的，當(dāng)且僅當(dāng)公式f=(∨y1∨y2)∧(∨