計算理論NP完全性

1第7章NP完全性楊瑩冷芳玲第7章NP完全性7.1NP完全性定義7.2NP完全問題7.3NP完全性的計算討論237.1NP完全性定義7-1

語言L是NP完全的，若它滿足下面兩個條件：（1）L∈NP；（2）NP中的每個LA都多項式時間可歸約為L。7.2NP完全問題定理7-19[庫克—列文定理]

可滿足問題SAT是NP完全的。證明：NP中的每一個語言都可以多項式時間歸約到SAT。從NP中任取一個語言L，設(shè)MN={Q,Σ,Γ,δ,q0,B,F}是nk多項式時間內(nèi)判定L的非確定型圖靈機，其中k是常數(shù)。對于MN的任意輸入w，在多式時間內(nèi)構(gòu)造公式

Φ，使得w∈L

?

Φ∈SAT。47.2NP完全問題設(shè)f是由w到Φ的歸約，下面開始描述歸約f。

考慮MN在w上的執(zhí)行過程。定義MN在w上的畫面是一張nknk表格，其中行代表MN在輸入上的一個計算分支的瞬時描述。并約定每一個ID都以“#”開始和結(jié)束。當(dāng)然畫面的第一行是初始ID，每一行都根據(jù)MN的轉(zhuǎn)移函數(shù)從上一行得到，如果畫面的某一行是接受ID，則稱該畫面是接受的。57.2NP完全問題我們把畫面nknk個的格子中每一格稱為一個單元。第i行第j列的單元稱為cell[i,j]，它應(yīng)包含C=Q∪

{#}中的一個符號。定義變量xi,j,s（1≤i≤nk,1≤j≤nk,s∈C）表示單元中的內(nèi)容。xi,j,s=1，意味著cell[i,j]包含s。67.2NP完全問題77.2NP完全問題現(xiàn)在設(shè)計公式Φ

，使得變量的一個滿足賦值確實對應(yīng)MN在w上的一個接受畫面。為此要滿足以下4點：每個單元只能包含一個符號；第一行為初始ID存在接受ID表的每一行都對應(yīng)于從上一行的ID、按照MN的規(guī)則、合法轉(zhuǎn)移得到ID。87.2NP完全問題97.2NP完全問題7.2NP完全問題c1c2c3c4c5c611現(xiàn)在證明上面由w到Φ的映射可以在多項式內(nèi)完成。畫面是一個nknk的表格，所以它包含n2k個單元，每個單元有與它相關(guān)的l個變量，l=|C|，因為l只依賴于MN，所以變量的總數(shù)是O(n2k)。7.2NP完全問題對畫面的每個單元，公式

Фcell包含固定長度的公式片段，故長度為O(n2k)，

Фstart對頂行的每個單元包含一個片段，所以長度為O(nk)，

Фmove和

Фaccept對畫面的每個單元包含固定長度的公式片段，所以它們的長度為O(n2k)，于是

Ф總長度為O(n2k)，因此可在多項式時間內(nèi)從w生成Ф

，所以，SAT是NP完全問題。█127.2NP完全問題3SAT問題：將布爾變量或其非稱為文字，將由三個文字構(gòu)成的子句組成的合取范式推論7-33SAT是NP完全的。證明：證明SAT多項式時間歸約到3SAT。137.2NP完全問題

NodeCover問題：若G是無向圖,k是一整數(shù)，則G的頂點覆蓋問題是否存在最小的一個節(jié)點子集M，使得｜M｜≤k，且G的每條邊都與子集M的節(jié)點之一關(guān)聯(lián)。注意頂點覆蓋問題要求最小的頂點覆蓋規(guī)模。147.2NP完全問題頂點覆蓋問題（NodeCover）是NP完全的我們可以給出一個3SAT到這個問題的多項式時間內(nèi)運算的歸約，即把布爾公式Φ

映射為<G,k>，其中G是一個圖，k是一個正數(shù)，表示G的頂點覆蓋子集的節(jié)點數(shù)。為此，（1）對于Φ

中的每個布爾變元x對應(yīng)G的一條邊，邊的兩個頂點記為x和?x。當(dāng)x賦值為TRUE時，表示對應(yīng)的覆蓋選擇x；當(dāng)x賦值為FALSE時，表示對應(yīng)的覆蓋選擇?x。157.2NP完全問題（2）Φ子句中的三個文字對應(yīng)于G的三個節(jié)點，這三節(jié)點相互連接，并分別于(1)中具有相同標(biāo)記的節(jié)點相連。167.2NP完全問題易見，3SAT可多項式時間歸約為頂點覆蓋問題。不難證明

Φ可滿足當(dāng)且僅當(dāng)G中有k=m+2l個節(jié)點的頂點覆蓋，其中m是Φ

的變元數(shù)，l是Φ子句數(shù)。177.2NP完全問題對于一個滿足賦值，（1）把變量構(gòu)件中真文字節(jié)點放入M中，（2）把子句中，除為真的文字外的另兩個文字加入M中?？梢奙中G的一個覆蓋。187.2NP完全問題對于G的覆蓋M，把M中的文字置為真。因為M中包含每個變量構(gòu)件的一個節(jié)點和子句構(gòu)件的兩個節(jié)點，所以這個賦值滿點3SAT。197.2NP完全問題Clique（團）是圖的一個子圖，其中任何兩點都有邊相連。K-Clique問題：給定<G,k>,G是無向圖，G中包含至少k節(jié)點的團嗎？k-Clique是NP完全的證明：（1）k-Clique是NP問題（2）3SAT≤pk-Clique207.2NP完全問題設(shè)Φ

是3SAT公式，子句數(shù)是k，則G中的節(jié)點分成k組，每組三個節(jié)點，稱為三元組，每個三元組對應(yīng)Φ中的一個子句。G中的邊定義為：不同三元組的節(jié)點，若不是相反文字，則兩兩相連；三元組內(nèi)節(jié)點間無邊?？梢姡?）Φ有一可滿足賦值，G存在一個k-團；（2）G存在一個k-團，Φ可滿足。217.2NP完全問題SUBSET-SUM（子集和）問題:有一個數(shù)集x1,x2,…,xk和一個目標(biāo)數(shù)t，要判定數(shù)集是否包含一個加起來等于t的子集。子集和問題是NP完全的（1）子集和問題屬于NP類（2）3SAT≤pSUBSET-SUM227.2NP完全問題HAMPATH(Hamilton路)問題也是NP完全的。（1）HAMPATH問題屬于NP類；（2）3SAT≤pHAMPATH。從Φ構(gòu)造圖G：把變量xi表示為鉆石結(jié)構(gòu)，把子句ci

表示為節(jié)點。237.2NP完全問題每個鉆石結(jié)構(gòu)都包含一行水平節(jié)點，它們由雙向邊連接起來。247.2NP完全問題如果變量xi出現(xiàn)在子句cj中，就把圖中兩條從第i個鉆石的第j對節(jié)點到第j個子句節(jié)點的邊添加進(jìn)去。如果變量?xi出現(xiàn)在子句cj中，就把圖中兩條從第i個鉆石的第j對節(jié)點到第j個子句節(jié)點的邊添加進(jìn)去。257.2NP完全問題HittingSet問題：給定集合A的子集的集合C和整數(shù)k，A是否有一個子集A’,|A’|=k,且對于C中的任意元素（A的子集），A’至少