2024年-NP完全問(wèn)題證明幻燈片

幾個(gè)NP完全問(wèn)題12什么是NP完全問(wèn)題NP完全問(wèn)題，是世界七大數(shù)學(xué)難題之一。NP的英文全稱是Non-deterministicPolynomial的問(wèn)題，即多項(xiàng)式復(fù)雜程度的非確定性問(wèn)題。簡(jiǎn)單的寫法是NP=P？，問(wèn)題就在這個(gè)問(wèn)號(hào)上，到底是NP等于P，還是NP不等于P22024/5/5七大數(shù)學(xué)難題這七個(gè)“千年大獎(jiǎng)問(wèn)題”是：NP完全問(wèn)題、霍奇猜想、龐加萊猜想、黎曼假設(shè)、楊－米爾斯理論、納衛(wèi)爾－斯托可方程、BSD猜想千年大獎(jiǎng)問(wèn)題美國(guó)麻州的克雷（Clay）數(shù)學(xué)研究所于2000年5月24日在巴黎法蘭西學(xué)院宣布了一件被媒體炒得火熱的大事：對(duì)七個(gè)“千年數(shù)學(xué)難題”的每一個(gè)懸賞一百萬(wàn)美元。其中有一個(gè)已被解決(龐加萊猜想),還剩六個(gè).（龐加萊猜想，已由俄羅斯數(shù)學(xué)家格里戈里·佩雷爾曼破解。我國(guó)中山大學(xué)朱熹平教授和旅美數(shù)學(xué)家、清華大學(xué)兼職教授曹懷東做了證明的封頂工作。）32024/5/5什么是NP完全問(wèn)題NP完全問(wèn)題排在百萬(wàn)美元大獎(jiǎng)的首位，足見(jiàn)他的顯赫地位和無(wú)窮魅力。在一個(gè)周六的晚上，你參加了一個(gè)盛大的晚會(huì)。由于感到局促不安，你想知道這一大廳中是否有你已經(jīng)認(rèn)識(shí)的人。你的主人向你提議說(shuō)，你一定認(rèn)識(shí)那位正在甜點(diǎn)盤附近角落的女士羅絲。不費(fèi)一秒鐘，你就能向那里掃視，并且發(fā)現(xiàn)你的主人是正確的。然而，如果沒(méi)有這樣的暗示，你就必須環(huán)顧整個(gè)大廳，一個(gè)個(gè)地審視每一個(gè)人，看是否有你認(rèn)識(shí)的人。生成問(wèn)題的一個(gè)解通常比驗(yàn)證一個(gè)給定的解時(shí)間花費(fèi)要多得多。這是這種一般現(xiàn)象的一個(gè)例子。與此類似的是，如果某人告訴你，數(shù)１３，７１７，４２１可以寫成兩個(gè)較小的數(shù)的乘積，你可能不知道是否應(yīng)該相信他，但是如果他告訴你它可以因式分解為３６０７乘上３８０３，那么你就可以用一個(gè)袖珍計(jì)算器容易驗(yàn)證這是對(duì)的。人們發(fā)現(xiàn)，所有的完全多項(xiàng)式非確定性問(wèn)題，都可以轉(zhuǎn)換為一類叫做滿足性問(wèn)題的邏輯運(yùn)算問(wèn)題。既然這類問(wèn)題的所有可能答案，都可以在多項(xiàng)式時(shí)間內(nèi)計(jì)算，人們于是就猜想，是否這類問(wèn)題，存在一個(gè)確定性算法，可以在多項(xiàng)式時(shí)間內(nèi)，直接算出或是搜尋出正確的答案呢？這就是著名的NP=P？的猜想。不管我們編寫程序是否靈巧，判定一個(gè)答案是可以很快利用內(nèi)部知識(shí)來(lái)驗(yàn)證，還是沒(méi)有這樣的提示而需要花費(fèi)大量時(shí)間來(lái)求解，被看作邏輯和計(jì)算機(jī)科學(xué)中最突出的問(wèn)題之一（斯蒂文·考克于１９７１年陳述）42024/5/58.5 一些典型的NP完全問(wèn)題5部分NP完全問(wèn)題樹2024/5/58.5.1合取范式的可滿足性問(wèn)題

（CNF-SAT）6要證明CNF-SAT∈NPC，只要證明在Cook定理中定義的布爾表達(dá)式A，…，G或者已是合取范式，或者有的雖然不是合取范式，但可以用布爾代數(shù)中的變換方法將它們化成合取范式，而且合取范式的長(zhǎng)度與原表達(dá)式的長(zhǎng)度只差一個(gè)常數(shù)因子。

問(wèn)題描述：給定一個(gè)合取范式α，判定它是否可滿足。如果一個(gè)布爾表達(dá)式是一些因子和之積，則稱之為合取范式，簡(jiǎn)稱CNF(ConjunctiveNormalForm)。這里的因子是變量或。例如：就是一個(gè)合取范式，而就不是合取范式。2024/5/58.5.23元合取范式的可滿足性問(wèn)題

（3-SAT）7證明思路：

3-SAT∈NP是顯而易見(jiàn)的。為了證明3-SAT∈NPC，只要證明CNF-SAT∝p3-SAT，即合取范式的可滿足性問(wèn)題可在多項(xiàng)式時(shí)間內(nèi)變換為3-SAT。

問(wèn)題描述：給定一個(gè)3元合取范式α，判定它是否可滿足。

2024/5/5對(duì)于一個(gè)合取范式，若每個(gè)子句有且僅有3個(gè)變?cè)獣r(shí)，它的可滿足性問(wèn)題便稱為3SAT問(wèn)題。定理

3SAT問(wèn)題屬于NPC。下證82024/5/58.5.3團(tuán)問(wèn)題CLIQUE

9證明思路：

已經(jīng)知道CLIQUE∈NP。通過(guò)3-SAT∝pCLIQUE來(lái)證明CLIQUE是NP難的，從而證明團(tuán)問(wèn)題是NP完全的。

問(wèn)題描述：給定一個(gè)無(wú)向圖G=(V，E)和一個(gè)正整數(shù)k，判定圖G是否包含一個(gè)k團(tuán)，即是否存在，V’

V，|V’|=k，且對(duì)任意u，w∈V’有(u，w)∈E。2024/5/58.5.4頂點(diǎn)覆蓋問(wèn)題

（VERTEX-COVER）

10證明思路：

首先，VERTEX-COVER∈NP。因?yàn)閷?duì)于給定的圖G和正整數(shù)k以及一個(gè)“證書”V’，驗(yàn)證|V’|=k，然后對(duì)每條邊(u，v)∈E，檢查是否有u∈V’或v∈V’，顯然可在多項(xiàng)式時(shí)間內(nèi)完成。其次，通過(guò)CLIQUE∝pVERTEX-COVER來(lái)證明頂點(diǎn)覆蓋問(wèn)題是NP難的。

問(wèn)題描述：給定一個(gè)無(wú)向圖G=(V，E)和一個(gè)正整數(shù)k，判定是否存在V’

V，|V’|=k，使得對(duì)于任意(u，v)∈E有u∈V’或v∈V’。如果存在這樣的V’，就稱V’為圖G的一個(gè)大小為k頂點(diǎn)覆蓋。2024/5/5

證將3SAT變換到VC.設(shè)U={u1,u2,...,un},C={c1,c2,...,cm}是3SAT的實(shí)例.如下構(gòu)造圖G,分量設(shè)計(jì)法.

真值安排分量:Ti=(Vi,Ei),1in,其中Vi={ui,ūi},Ei={{ui,ūi}}任意覆蓋必至少包含ui或ūi中的一個(gè),否則不能覆蓋邊{ui或ūi}.

滿足性檢驗(yàn)分量:Sj=(Vj’,Ej’),1

j

m,其中

Vj’={a1[j],a2[j],a3[j]}Ej’={{a1[j],a2[j]},{a1[j],a3[j]},{a2[j],a3[j]}}覆蓋至少包含Vj’中的兩個(gè)頂點(diǎn),否則不能覆蓋Ej’中的三角形8.5.4頂點(diǎn)覆蓋問(wèn)題

（VERTEX-COVER）

112024/5/5聯(lián)絡(luò)邊:

溝通分量之間的關(guān)系對(duì)于每個(gè)子句cj,設(shè)cj={xj,yj,zj},則

Ej’’={{a1[j],xj},{a2[j],yj},{a3[j],zj}}G=(V,E)V=(V1

V2

...

Vn)(V1’

V2’

...

Vm’)E=E1

E2

...

En)(E1’

E2’

...

Em’)

(E1’’

E2’’

...

Em’’)K=n+2m顯然構(gòu)造可在多項(xiàng)式時(shí)間完成8.5.4頂點(diǎn)覆蓋問(wèn)題

（VERTEX-COVER）

122024/5/5重慶調(diào)查公司重慶私人偵探奀莒嗶132例如U={u1,u2,u3,u4},C={{u1,ū3,ū4},{ū1,u2,ū4}},則G如下，K=4+2×2=88.5.4頂點(diǎn)覆蓋問(wèn)題

（VERTEX-COVER）

142024/5/5

設(shè)V’是V中不超過(guò)K的頂點(diǎn)覆蓋,則V’中必包含Ti中的一個(gè)頂點(diǎn)和每個(gè)Ej’中的兩個(gè)頂點(diǎn),至少要n+2m個(gè)頂點(diǎn).而K=n+2m,故V’中一定只包含每個(gè)Ti中的一個(gè)頂點(diǎn)和每個(gè)Ej’中的兩個(gè)頂點(diǎn).

如下得到賦值

uiV’

t(ui)=T

ūiV’

t(ui)=FEj’’中的三條邊有兩條被Vj’V’中的頂點(diǎn)覆蓋,第三條必被V’

Vi中的頂點(diǎn)覆蓋.這表示在Vi中的這個(gè)頂點(diǎn)對(duì)應(yīng)的文字取真.所以子句cj被滿足.從而C被滿足.

設(shè)t:U{T,F}是滿足C的一組賦值.若t(ui)=T,則在Ti中取頂點(diǎn)ui,否則取ūi.因?yàn)閠滿足子句cj,在Ej’’中的三條聯(lián)絡(luò)邊中至少有一條被覆蓋,那么取Ej’’中的另兩條邊的端點(diǎn)作為V’中的端點(diǎn)即可.

8.5.4頂點(diǎn)覆蓋問(wèn)題

（VERTEX-COVER）

152024/5/5實(shí)例：有窮集A，

a

A,s(a)

Z+.問(wèn)：是否存在A’

A，使得證：顯然均分是NP類問(wèn)題。下面將3DM變換到均分問(wèn)題設(shè)W,X,Y,M

WX

Y是3DM的實(shí)例，其中|W|=|X|=|Y|=q，

W={w1,w2,…,wq}X={x1,x2,…,xq}Y={y1,y2,…,yq}M={m1,m2,…,mk}8.5.5.均分

NPC162024/5/5w1w2…wqx1x2…xqy1y2…yqB的段數(shù)與s(ai)一樣，每段的最右位為1，其它為0構(gòu)造A，|A|=k+2對(duì)應(yīng)于每個(gè)mi=(wf(i),xg(i),yh(i))有ai.s(ai)為二進(jìn)制數(shù)，分成3q段，每段有p=

log(k+1)

位,共計(jì)3pq位，每段對(duì)應(yīng)一個(gè)WX

Y中的元素.Wf(i),xg(i),yh(i)

所代表的段的最右位為1，其它為0.注：plog(k+1)，2pk+1，k2p

1,

當(dāng)k個(gè)1相加時(shí)不會(huì)產(chǎn)生段之間的進(jìn)位令8.5.5.均分

NPC172024/5/5例如：W={w1,w2},X={x1,x2},Y={y1,y2},M={(w1,x2,y2),(w1,x2,y1),(w2,x1,y1)}p=log(3+1)=2元素a1,a2,a3分別對(duì)應(yīng)

(w1,x2,y2),(w1,x2,y1),(w2,x1,y1)s(a1)=010000010001=210+24+20

s(a2)=010000010100=210+24+22s(a3)=000101000100=28+26+22

B=0101010101018.5.5.均分

NPC182024/5/5子集A’={ai:1

i

k}滿足

當(dāng)且僅當(dāng)M’={mi:ai

A’}是M的匹配A的最后兩個(gè)元素b1,b2

8.5.5.均分

NPC192024/5/5假設(shè)A’

A使得A’和A-A’的元素大小之和相等，即由于b1,b2不在同一子集，8.5.5.均分

NPC202024/5/5反之，若子集M’構(gòu)成M的匹配，則

A’={b1}

{ai:mi

M’}滿足因此A’-{b1}的元素對(duì)應(yīng)的三元組構(gòu)成M的匹配考慮包含b1的子集A’,必有8.5.5.均分

NPC212024/5/5限制法

三元集合的恰當(dāng)覆蓋(X3C)

最小覆蓋問(wèn)題集中集子圖同構(gòu)問(wèn)題有界度的生成樹

0-1背包Knapsack

多處理機(jī)調(diào)度8.5.6、NP完全性的證明方法222024/5/5

局部替換法

3SAT

兩點(diǎn)間的Hamilton通路問(wèn)題區(qū)間排序分量設(shè)計(jì)法最小拖延排序8.5.6、NP完全性的證明方法232024/5/5限制法：通過(guò)對(duì)問(wèn)題的實(shí)例加以限制得到一個(gè)已知

NP完全問(wèn)題的實(shí)例.例1三元集合的恰當(dāng)覆蓋(X3C)

實(shí)例：有窮集S,|S|=3q,S的三元子集的集合C

問(wèn)：是否有C’

C,使得S的每個(gè)元素恰好出現(xiàn)在C’的一個(gè)成員中.

證明：限制

S=WX

Y|W|=|X|=|Y|=qC={{w,x,y}|(w,x,y)W

X

Y}則|C’|=q,且C’中任兩個(gè)元素都不交，成為3DM問(wèn)題8.5.6、NP完全性的證明方法242024/5/5例2最小覆蓋問(wèn)題實(shí)例：集合S的子集的集合C，正整數(shù)K.

問(wèn)：C是否有S的大小不超過(guò)K的覆蓋，即是否包含子集C’

C使得|C’|=K且C’=S？證明：限制c

C,|c|=3,|S|=3K,則為X3C問(wèn)題.例3集中集實(shí)例：集合S的子集的集合C，正整數(shù)K

問(wèn)：S是否包含C的大小不超過(guò)K的集中集（hittingset）,即是否有子集S’

S,使得|S’|K,且S’至少包含C的每個(gè)子集的一個(gè)元素？證明：限制c

C,|c|=2,令V=S,E=C,則構(gòu)成圖G=(V,E)的頂點(diǎn)覆蓋問(wèn)題.8.5.6、NP完全性的證明方法252024/5/5例4子圖同構(gòu)問(wèn)題實(shí)例：圖G=(V1,E1),H=(V2,E2)

問(wèn)：G中是否有同構(gòu)于H的子圖，即是否有子集V

V1,EE1,使得|V|=|V2|,|E|=|E2|,且存在雙射函數(shù)f：V2

V,使得

{u,v}

E2

{f(u),f(v)}

E?

證明：限制H為完全圖，且|V2|=J,則該問(wèn)題是團(tuán)的問(wèn)題.例5有界度的生成樹實(shí)例：圖G=(V,E),正整數(shù)K=|V|1

問(wèn)：G是否包含一棵頂點(diǎn)度數(shù)不超過(guò)K的生成樹，即是否有子集E’

E,|E’|=|V|

1,圖G’=(V,E’)是連通的，且V中每個(gè)頂點(diǎn)至多包含在E’的K條邊中？證明：限制K=2，則為Hamilton通路問(wèn)題8.5.6、NP完全性的證明方法262024/5/5例60-1背包Knapsack

實(shí)例：有窮集U，

u

U,大小s(u)Z+,價(jià)值

v(u)Z+,大小的約束BZ+,價(jià)值目標(biāo)KZ+.

問(wèn)：是否有子集U’

U，使得證明：限制

u

U,則成為均分問(wèn)題8.5.6、NP完全性的證明方法272024/5/5例7多處理機(jī)調(diào)度實(shí)例：有窮任務(wù)集A，

a

A,長(zhǎng)度l(a)Z+,處理機(jī)臺(tái)數(shù)

mZ+,截止時(shí)間DZ+.

問(wèn)：是否存在不交的集合A1,A2,…,Am,使得證明：限制則成為均分問(wèn)題.8.5.6、NP完全性的證明方法282024/5/5局部替換法：選擇已知NP完全問(wèn)題的實(shí)例中的某些元素作為基本單元，然后把每個(gè)基本單元替換成指定結(jié)構(gòu)，從而得到目標(biāo)問(wèn)題的對(duì)應(yīng)實(shí)例.

例83SAT

已知問(wèn)題：SAT

目標(biāo)問(wèn)題：3SAT

基本單元：子句

子句集例9兩點(diǎn)間的Hamilton通路實(shí)例：G=(V,E)，u,v

V.

問(wèn)：G中是否存在一條從u到v的Hamilton通路？已知問(wèn)題：HC

目標(biāo)問(wèn)題：兩點(diǎn)間Hamilton通路基本單元：頂點(diǎn)a

u,v

證：對(duì)于HC的任一實(shí)例，任選頂點(diǎn)a,用u,v代替a,即

G’=(V’,E’),V’=(V{a})

{u,v}E’=(E{{a,v’}|{a,v’}

E})

{{v,v’},{u,v’}|{a,v’}

E}8.5.6、NP完全性的證明方法292024/5/5

GG’G有一條Hamilton回路當(dāng)且僅當(dāng)G’有一條從u到v的Hamilton通路替換實(shí)例8.5.6、NP完全性的證明方法302024/5/5例10區(qū)間排序?qū)嵗河懈F任務(wù)集T,

t

T,開(kāi)放時(shí)間r(t),截止時(shí)間d(t),需要時(shí)間l(t),其中r(t)N,d(t),l(t)Z+.

問(wèn)：是否存在關(guān)于T的可行調(diào)度，即是否存在函數(shù):T

N使得t

T滿足：

(t)

r(t)

(t)+l(t)d(t)

t’

T

{t},

(t’)+l(t’)(t)或(t)+l(t)(t’)?

已知問(wèn)題：均分

目標(biāo)問(wèn)題：區(qū)間排序基本單元：A中元素

T中的任務(wù)312024/5/5實(shí)施者,若B為偶數(shù)，則存在均分證設(shè)A和s(a)

Z+(a

A)為均分的實(shí)例.

a

A將a替換成taT,d(ta)=B+1，l(ta)=s(a)，其中B為奇數(shù)，則不能調(diào)度8.5.6、NP完全性的證明方法322024/5/5分量設(shè)計(jì)法根據(jù)目標(biāo)問(wèn)題的實(shí)例設(shè)計(jì)分量(分量的成分與目標(biāo)問(wèn)題相關(guān))，實(shí)現(xiàn)已知NPC問(wèn)題的實(shí)例（分量的功能與已