2024年-NP完全問題證明幻燈片

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

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

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

（3-SAT）7證明思路：

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

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

2024/5/5對于一個合取范式，若每個子句有且僅有3個變元時，它的可滿足性問題便稱為3SAT問題。定理

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

9證明思路：

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

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

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

（VERTEX-COVER）

10證明思路：

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

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

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

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

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

滿足性檢驗分量: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’中的兩個頂點,否則不能覆蓋Ej’中的三角形8.5.4頂點覆蓋問題

（VERTEX-COVER）

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

溝通分量之間的關(guān)系對于每個子句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)造可在多項式時間完成8.5.4頂點覆蓋問題

（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頂點覆蓋問題

（VERTEX-COVER）

142024/5/5

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

如下得到賦值

uiV’

t(ui)=T

ūiV’

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

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

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

8.5.4頂點覆蓋問題

（VERTEX-COVER）

152024/5/5實例：有窮集A，

a

A,s(a)

Z+.問：是否存在A’

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

WX

Y是3DM的實例，其中|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對應(yīng)于每個mi=(wf(i),xg(i),yh(i))有ai.s(ai)為二進(jìn)制數(shù)，分成3q段，每段有p=

log(k+1)

位,共計3pq位，每段對應(yīng)一個WX

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

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

1,

當(dāng)k個1相加時不會產(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分別對應(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的最后兩個元素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}的元素對應(yīng)的三元組構(gòu)成M的匹配考慮包含b1的子集A’,必有8.5.5.均分

NPC212024/5/5限制法

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

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

0-1背包Knapsack

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

局部替換法

3SAT

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

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

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

問：是否有C’

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

證明：限制

S=WX

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

X

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

問：C是否有S的大小不超過K的覆蓋，即是否包含子集C’

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

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

問：S是否包含C的大小不超過K的集中集（hittingset）,即是否有子集S’

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

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

問：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,則該問題是團(tuán)的問題.例5有界度的生成樹實例：圖G=(V,E),正整數(shù)K=|V|1

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

E,|E’|=|V|

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

實例：有窮集U，

u

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

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

問：是否有子集U’

U，使得證明：限制

u

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

a

A,長度l(a)Z+,處理機臺數(shù)

mZ+,截止時間DZ+.

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

例83SAT

已知問題：SAT

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

基本單元：子句

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

V.

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

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

u,v

證：對于HC的任一實例，任選頂點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通路替換實例8.5.6、NP完全性的證明方法302024/5/5例10區(qū)間排序?qū)嵗河懈F任務(wù)集T,

t

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

問：是否存在關(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’)?

已知問題：均分

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

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

Z+(a

A)為均分的實例.

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ù)目標(biāo)問題的實例設(shè)計分量(分量的成分與目標(biāo)問題相關(guān))，實現(xiàn)已知NPC問題的實例（分量的功能與已