計(jì)算理論NP完全性

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

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

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

Φ，使得w∈L

?

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

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

{#}中的一個(gè)符號(hào)。定義變量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è)計(jì)公式Φ

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

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

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

Фmove和

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

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

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

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

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

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

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

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

是3SAT公式，子句數(shù)是k，則G中的節(jié)點(diǎn)分成k組，每組三個(gè)節(jié)點(diǎn)，稱為三元組，每個(gè)三元組對應(yīng)Φ中的一個(gè)子句。G中的邊定義為：不同三元組的節(jié)點(diǎn)，若不是相反文字，則兩兩相連；三元組內(nèi)節(jié)點(diǎn)間無邊?？梢姡?）Φ有一可滿足賦值，G存在一個(gè)k-團(tuán)；（2）G存在一個(gè)k-團(tuán)，Φ可滿足。217.2NP完全問題SUBSET-SUM（子集和）問題:有一個(gè)數(shù)集x1,x2,…,xk和一個(gè)目標(biāo)數(shù)t，要判定數(shù)集是否包含一個(gè)加起來等于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é)點(diǎn)。237.2NP完全問題每個(gè)鉆石結(jié)構(gòu)都包含一行水平節(jié)點(diǎn)，它們由雙向邊連接起來。247.2NP完全問題如果變量xi出現(xiàn)在子句cj中，就把圖中兩條從第i個(gè)鉆石的第j對節(jié)點(diǎn)到第j個(gè)子句節(jié)點(diǎn)的邊添加進(jìn)去。如果變量?xi出現(xiàn)在子句cj中，就把圖中兩條從第i個(gè)鉆石的第j對節(jié)點(diǎn)到第j個(gè)子句節(jié)點(diǎn)的邊添加進(jìn)去。257.2NP完全問題HittingSet問題：給定集合A的子集的集合C和整數(shù)k，A是否有一個(gè)子集A’,|A’|=k,且對于C中的任意元素（A的子集），A’至少