第十章 NP完全問題

算法設計與分析

AlgorithmsDesignandAnalysis

趙廷剛蘭州城市學院數學學院2013.3本章內容10.1引言10.2P類10.3NP類10.4NP完全問題10.5co-NP類10.6NPI類10.7四種類之間的關系10.1引言有這樣一類問題：至今沒有找到有效算法，而且將來也不大可能發(fā)現它們的有效算法。設Π是任意問題，如果對問題Π存在一個算法，它的時間復雜性是O(nk),其中n是輸入大小，k是非負整數，我們說存在著求解問題Π的多項式時間算法?，F實世界中的許多有趣問題并不屬于這個范疇，即求解這些問題所需要的時間量是要用指數或超指數函數(2n或n!)來測度。計算機科學界的共識：存在多項式時間算法的問題是易于求解的，而那些不大可能存在多項式時間算法的問題是難解的。NP完全問題是難解問題的一個子類。它包含許許多多問題，其中還有數百個著名的問題，它們有一個共同特性，即如果它們中的一個是多項式可解的，那么所有其它的問題也是多項式可解的。非常有趣的是，它們中的許多是普通的現實問題，就是說它們來源于現實世界的實際應用問題。此外，現存的求解這些問題的算法的運行時間，對于中等大小的輸入也需要幾百或幾千年。判定問題：問題使它的解只有兩個結論：是或否。最優(yōu)化問題：問題關心某個量的最大化或最小化。例10.1

設S是一個實數序列，ELEMENTUNIQUENESS問題為，是否S中的所有數都是不同的.判斷問題：ELEMENTUNIQUENESS

輸入：一個整數序列S.問題：在S中存在兩個相等的元素嗎？最優(yōu)問題：ELEMENTCOUNT

輸入：一個整數序列S.輸出：一個在S中頻度最高的元素。這個問題在最優(yōu)時間O(nlogn)

解決，它是易解的。例10.2

給出一個無向圖G=(V,E)，用k種顏色對G著色是這樣的問題：對于V中的每一個頂點用k種顏色中的一種對它著色，使圖中沒有兩個相鄰頂點有相同的顏色.判斷問題：COLORING

輸入：一個無向圖G=(V,E)和一個正整數k≥1.問題：G可以k著色嗎？即G最多可以用k種顏色著色嗎？最優(yōu)問題：CHROMATICNUMBER

輸入：一個無向圖G=(V.E).輸出：G的色數。這個問題是難解的。如果k=3，就是3著色問題。對一個圖著色，使圖中沒有兩個相鄰的頂點有相同的顏色，所需的最少顏色數，稱為G的色數，記為χ(G).例10.3

給出一個無向圖G=(V,E)，對于某個正整數k，G中大小為k的團集是指G中有k個頂點的一個完全子圖。判斷問題：CLIQUE

輸入：一個無向圖G=(V,E)和一個正整數k.問題：G有大小為k的團集嗎？最優(yōu)問題：MAX-CLIQUE

輸入：一個無向圖G=(V,E).輸出：一個正整數k，它是G中最大團集的大小。10.2P類定義10.1

設A是求解問題∏的一個算法，如果在展示問題∏的一個實例時，在整個執(zhí)行過程中每一步都只有一種選擇，則稱A是確定性算法。因此如果對于同樣的輸入，實例一遍又一遍地執(zhí)行，它的輸出從不改變。定義10.2

判斷問題的P類由這樣的問題組成，它們的yes/no解可以用確定性算法在運行多項式步數內得到，例如在O(nk)步內得到，其中k是某個非負整數，n是輸入大小。

不是每一個判定問題都能夠在多項式的時間內求解。

某些判斷問題是不能用任何算法求解的。這些問題稱為不可判定問題。排序問題：給出一個n個整數的表，它們是否按非降序排列？不相交集問題：給出兩個整數集合，它們的交集是否為空？最短路問題：給出一個邊上有正權的有向圖G=(V,E),兩個特異的頂點s,t∈V和一個正整數k，在s和t之間是否存在一條路徑，它的長度最多是k。2著色問題：給出一個無向圖G,它是否可2著色？2可滿足問題：給出一個合取范式(CNF)形式的布爾表達式f，這里每個子句恰好由兩個文字組成。問f是可滿足的嗎？下列問題屬于P類：如果對任意問題類C，問題∏的補也在C中，我們說問題類∏∈C在補運算下是封閉的。例如，2著色問題的補可以陳述如下：給出一個圖G，它是不2可著色的嗎？我們稱這個問題是NOT-2-COLOR問題。

可以證明，NOT-2-COLOR問題是屬于P類的。即2著色問題在補運算下是封閉的。定理10.1

P類問題在補運算下是封閉的。10.3NP類不確定性算法

設對于輸入x，一個不確定算法由兩步組成：(a)猜測階段（非確定）。在這個階段產生一個任意字符串y，它可能對應于輸入實例的一個解，也可以不對應解。事實上，它甚至可能不是所求解的合適形式，它可能在不確定性算法的不同次運行中不同。它僅僅要求在多項式步數內產生這個串，即在O(ni)時間內，這里n=|x|，i是非負整數。對許多問題，這一階段可以在線性時間內完成。(b)驗證階段（確定）。驗證兩件事。首先，檢驗y是否有合適的形式，如果不是，則算法停下來并回答no；另一方面，如果y有合適形式，那么算法繼續(xù)檢查它是否是問題實例x的解，如果它確實是實例x的解，那么它停下并且回答yes，否則它停下并回答no。我們要求這個階段在多項式步數內完成，即在時間O(nj)內完成,這里j是一個非負整數。定義10.3

判斷問題的NP類由這樣的問題組成:對于它們存在著多項式時間內運行的不確定性算法。設A是問題∏的一個不確定行算法，我們說A接受問題∏的實例I,當且僅當對于輸入I存在一個導致yes回答的猜測。換句話說，A接受I當且僅當可能在算法的某次執(zhí)行上它的驗證階段將回答yes。要強調的是，如果算法回答no，那么著并不意味著A不接受它的輸入，因為算法可能猜測了一個不正確的解。

至于一個不確定性算法的運行時間，它僅僅是兩個運行時間的和：猜測階段和驗證階段的時間。P類和NP類之間，有下面不同點：

P是一個判斷問題類，這些問題可以用一個確定性算法在多項式時間內判定或解出；NP是一個判斷問題類，這些問題可以用一個確定性算法在多項式時間內檢驗或驗證它的解。10.4NP完全問題

術語“NP完全”表示NP中判定問題的一個子類，它們在下述意義下是最難的，即如果它們中的一個被證明用多項式時間確定性算法可解，那么NP中的所有問題用多項式時間確定算法可解，即P=NP。定義10.4

設Π和Π’是兩個判斷問題。如果存在一個確定性算法A，它的行為如下，當給A展示問題Π的一個實例I,算法A可以把它變換為問題Π’的實例I’,使得當且僅當對I’回答yes時，對I回答yes,而且，這個變換必須在多項式時間內完成。那么我們說Π多項式時間歸約到Π’,用符號Π∝polyΠ’表示。定義10.6

一個判斷問題Π稱為是NP完全的，如果下列兩個條件同時成立：

(a)Π在NP中;

(b)對于NP中的每一個問題

Π’,Π’

∝polyΠ。定義10.5

一個判斷問題Π稱為是NP困難的，如果對NP中每一個問題Π’,

Π’

∝polyΠ表示。

這樣，在NP完全問題∏和NP困難問題∏’間的差別是：∏必須是NP類的而∏’可能不在NP中。10.4.1可滿足性問題合取范式(CNF)：給出一個布爾公式f,如果他是子句的合取，就稱它為合取范式(CNF).

例如：可滿足的(CNF)：一個公式如果對它的變元存在一個真值的指派是他為真，則稱為可滿足的。

因此，為了證明一個問題∏是NP完全問題，僅需證明下面兩條：(1)∏∈NP；(2)存在一個NP完全問題∏’,使∏’∝poly∏.10.4.2頂點覆蓋、獨立集和團集問題團集：給出一個無向圖G=(V,E)和一個正整數k,G包含一個大小為k的團集嗎？(一個G中大小為k的團集是G中k個頂點的一個完全子圖）。頂點覆蓋：給出一個無向圖G=(V,E)和一個正整數k,是否存在大小為k的子集C包含于V,使E中的每條邊至少和C中的一個頂點關聯(lián)？獨立集：給出一個無向圖G=(V,E)和一個正整數k,是否存在k個頂點的子集S包含于V，使得對于每一對頂點u,w∈S,(u,w)?E？可以證明以上三個問題都是