CHAPTER7 NP完全性

本文來自我的個(gè)人博客 https://www.zhangshenghai.com/posts/64398/

P問題、NP問題、NPC問題的概念

老師上課時(shí)強(qiáng)調(diào)過本章對(duì)于概念要特別清楚，因此首先給出這三個(gè)問題的概念：

  • P問題：能夠在多項(xiàng)式時(shí)間內(nèi)解決的問題。

  • NP問題：能夠在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證一個(gè)解的正確性的問題。

  • NPC問題：當(dāng)一個(gè)問題滿足下面兩個(gè)條件的時(shí)候，那么這個(gè)問題是NPC問題。

    • 首先，它是NP問題。
    • 其次，所有其他的NP問題都能夠在多項(xiàng)式時(shí)間內(nèi)歸約到此問題上（NP-hard）。

    NPC問題是NP問題的子集。

  • NP-hard問題：?jiǎn)栴}A不一定是一個(gè)NP問題，但是所有的NPC問題都可以在多項(xiàng)式時(shí)間內(nèi)轉(zhuǎn)化為A，則稱A為NP-hard問題。

    NPC問題一定是NP-hard問題。

一些典型的NP完全問題

通過問題變換的技巧，可以將2個(gè)不同問題的計(jì)算復(fù)雜性聯(lián)系在一起。這樣就可以將一個(gè)問題的計(jì)算復(fù)雜性歸約為另一個(gè)問題的計(jì)算復(fù)雜性，從而實(shí)現(xiàn)問題的計(jì)算復(fù)雜性歸約。

證明一個(gè)問題是NP完全問題分為兩個(gè)步驟：

  1. 證明該問題是NP問題。

  2. 證明NP問題中的每一個(gè)問題都能在多項(xiàng)式時(shí)間內(nèi)歸約為該問題。

    由于多項(xiàng)式問題具有傳遞性，因此只需證明一個(gè)已知的NP完全問題能夠在多項(xiàng)式時(shí)間內(nèi)歸約到該問題即可。

下圖給出了進(jìn)行NP完全證明的結(jié)構(gòu)，樹的根為CIRCUIT-SAT。

電路可滿足性問題（CIRCUIT-SAT）

由《算法導(dǎo)論》第二版引理34.5：電路可滿足性問題屬于NP類，以及引理34.6：電路可滿足性問題是NP難度的，結(jié)合NP完全性的定義可直接推出結(jié)論：

電路可滿足性問題是NP完全的。

合取范式的可滿足性問題（SAT）

證明：

  1. SAT ∈ NP:

    給定該問題的一個(gè)實(shí)例，用證書y={1, 1, 1}作為輸入，對(duì)于給定的布爾公式x，我們都能按照布爾公式的數(shù)學(xué)運(yùn)算規(guī)則在多項(xiàng)式時(shí)間內(nèi)求解出來。

  2. 在多項(xiàng)式時(shí)間內(nèi)將Circuit-SAT歸約到SAT：

    將電路中的輸入用布爾變?cè)硎?，將電路中的每一個(gè)邏輯門用布爾公式來對(duì)應(yīng)，就可以將Circuit-SAT問題歸約到SAT問題。

顯然，這是在多項(xiàng)式時(shí)間內(nèi)完成的，因此SAT是NP完全問題。

三元合取范式的可滿足性問題（3-CNF-SAT）

在這個(gè)問題的證明之前先補(bǔ)充一下合取范式（CNF）的定義。

如果一個(gè)布爾公式可表示為所有字句的“與”，且每個(gè)字句都是一個(gè)或多個(gè)文字的“或”，則稱該布爾公式為合取范式（CNF）。

如果公式中的每個(gè)字句恰好都有三個(gè)不同的文字，則稱該布爾公式為3-CNF。

例如，布爾公式
(x_1 \vee -x_1 \vee -x_2)\wedge(x_3 \vee x_2 \vee x_4)\wedge(-x_1 \vee -x3 \vee -x_4)
就是一個(gè)3-CNF，其三個(gè)字句中的第一個(gè)為(x_1 \vee -x_1 \vee -x_2)，它包含3個(gè)文字x_1，- x_1，-x_2。

證明：

  1. 3-CNF-SAT ∈ NP：

    這里的證明與上面的SAT問題是類似的。同樣給定一個(gè)證書y作為輸入，對(duì)于一個(gè)給定的合取范式，都可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證合取范式的值是1還是0。

  2. 在多項(xiàng)式時(shí)間內(nèi)將SAT歸約為3-CNF-SAT：

    由于這里的證明對(duì)離散數(shù)學(xué)的要求較高，且老師上課時(shí)也沒有細(xì)講這部分內(nèi)容，故只給出步驟，詳細(xì)的證明可參考《算法導(dǎo)論》第二版定理34.10。

    Ⅰ. 為輸入公式畫出一棵二叉“語法分析”樹，文字作為樹葉，連接詞作為內(nèi)部頂點(diǎn)。

    Ⅱ. 把每個(gè)字句變換為合取范式。

    Ⅲ. 繼續(xù)對(duì)公式進(jìn)行變換，使每個(gè)字句恰好有三個(gè)不同的文字。

從上面的步驟可以看出，SAT可以在多項(xiàng)式時(shí)間內(nèi)歸約到3-CNF-SAT，因此3-CNF-SAT是NP完全問題。

團(tuán)問題（CLIQUE）

證明：

  1. CLIQUE∈NP：

對(duì)于給定的圖G(V, E)，如果給定頂點(diǎn)集V'作為證書，我們可以驗(yàn)證對(duì)于任意一對(duì)頂點(diǎn)u, v∈V', 通過檢查邊(u, v)是否屬于E，從而驗(yàn)證V'是否是一個(gè)團(tuán)。顯然，這是在多項(xiàng)式時(shí)間內(nèi)完成的。

  1. 在多項(xiàng)式時(shí)間內(nèi)將3-CNF-SAT歸約到CLIQUE：

    給定一個(gè)含有k個(gè)字句的3-CNF，假定其是可滿足的，即3-CNF的結(jié)果為1。我們總是可以構(gòu)造一個(gè)3k個(gè)頂點(diǎn)的圖，構(gòu)造方法是在不同的三元組、且不是自己的非的節(jié)點(diǎn)之間連線。

    一共有k個(gè)分組，每個(gè)分組中的節(jié)點(diǎn)之間不能互相連接，而且這個(gè)3-CNF是可滿足的。那么每個(gè)分組都會(huì)有一個(gè)節(jié)點(diǎn)與其他分組的節(jié)點(diǎn)相連，將每個(gè)分組的選出的那個(gè)節(jié)點(diǎn)互相連接起來，就是最大團(tuán)。顯然，最大團(tuán)有k個(gè)節(jié)點(diǎn)。

    下面給出《算法導(dǎo)論》中的一個(gè)k=3的實(shí)例，圖中淺色的節(jié)點(diǎn)為每個(gè)分組中選出的節(jié)點(diǎn)。即3-CNF-SAT的一個(gè)可滿足賦值為x_2=0, x_3=1, x_1=0 或 1。

歸約過程在多項(xiàng)式內(nèi)可以完成，因此團(tuán)問題是NP完全問題。

頂點(diǎn)覆蓋問題（VERTEX-COVER）

證明：

  1. VERTEXT-COVER∈NP：

    對(duì)于給定的圖G(V, E)，如果給定頂點(diǎn)集V'作為證書，對(duì)于每條邊(u, v)∈E，我們可以檢查是否有u∈V'或v∈V'。這一驗(yàn)證在多項(xiàng)式時(shí)間內(nèi)即可完成。

  2. 在多項(xiàng)式時(shí)間內(nèi)將CLIQUE歸約到VERTEX-COVER：

    設(shè)G=(V, E)是CLIQUE的一個(gè)實(shí)例，設(shè)G的最大團(tuán)為V'，取圖G的補(bǔ)圖，設(shè)補(bǔ)圖上的邊為E'，補(bǔ)圖上的點(diǎn)為V-V'，那么V-V'是一個(gè)頂點(diǎn)覆蓋。

    原理：從E'中取任意的一條邊(u, v)，那么在G中，邊(u, v)是不存在的，那么u或v至少有一個(gè)在V-V'中。由于邊(u, v)是任意取自E'的，即在補(bǔ)圖中，任意一條邊上都至少有一個(gè)點(diǎn)是屬于V-V'的，即滿足頂點(diǎn)覆蓋的定義。

    下面給出一個(gè)例子，V' = {u, v, x, y}，V-V' = {z, w}。

同樣，這個(gè)歸約過程能夠在多項(xiàng)式時(shí)間內(nèi)完成，因此頂點(diǎn)覆蓋問題是NP完全問題。

哈密頓回路問題（HAM-CYCLE）

證明：

  1. DIR-HAM-CYCLE∈NP：

    對(duì)于一個(gè)給定的圖G(V, E)，我們可以簡(jiǎn)單驗(yàn)證一個(gè)頂點(diǎn)序列是否經(jīng)過所有頂點(diǎn)一次且僅一次，而且最后能夠回到源點(diǎn)。這個(gè)過程顯然是在多項(xiàng)式時(shí)間內(nèi)完成的。

  2. 在多項(xiàng)式時(shí)間內(nèi)將3-CNF-SAT歸約到DIR-HAM-CYCLE：

    1. 構(gòu)造一個(gè)能夠表達(dá)3-CNF中的文字和子句的圖結(jié)構(gòu)，每行中的節(jié)點(diǎn)代表3-CNF中的每個(gè)文字，如第一行中的節(jié)點(diǎn)都代表了x1，那么跨行之間的節(jié)點(diǎn)之間即可代表3-CNF中的字句。

      如果不清楚文字和字句的概念，可以參考上面3-CNF中關(guān)于合取范式的定義。

  1. 首先進(jìn)行一個(gè)定義：當(dāng)x_i=1時(shí)，遍歷的順序是從左到右，當(dāng)x_i=0時(shí)，遍歷的順序是從右到左。從最上面的源點(diǎn)出發(fā)，以某種方式連接這些點(diǎn)以滿足3-CNF，只要滿足圖中的3-CNF，那么這個(gè)圖就是有向哈密頓回路。這個(gè)過程是在多項(xiàng)式時(shí)間內(nèi)完成的。

接下來還要進(jìn)行另外一個(gè)歸約，才可以達(dá)到我們的目標(biāo)：

  1. HAM-CYCLE∈NP：

    與DIR-HAM-CYCLE的驗(yàn)證方法相同，這里不再贅述。

  2. 在多項(xiàng)式時(shí)間內(nèi)將DIR-HAM-CYCLE歸約到HAM-CYCLE：

    給定一個(gè)具有n個(gè)頂點(diǎn)的有向圖G=(V, E)，可以在多項(xiàng)式時(shí)間內(nèi)構(gòu)建一個(gè)具有3n個(gè)頂點(diǎn)的無向圖G'

以上兩個(gè)歸約都是在多項(xiàng)式時(shí)間內(nèi)完成的，故哈密頓回路是NP完全的。

旅行商問題（TSP）

證明：

  1. TSP∈ NP：

    給定該問題的一個(gè)實(shí)例，用n個(gè)頂點(diǎn)組成的回路作為證書，我們可以驗(yàn)證該回路是否只包含每個(gè)頂點(diǎn)一次，并且檢查各邊費(fèi)用之和是否小于k。這個(gè)過程能夠在多項(xiàng)式時(shí)間內(nèi)完成。

  2. 在多項(xiàng)式時(shí)間內(nèi)將哈密頓回路歸約到TSP：

    設(shè)G=(V, E)是HAM-CYCLE的一個(gè)實(shí)例，可以構(gòu)造對(duì)應(yīng)的一個(gè)TSP實(shí)例。建立一個(gè)完全圖G‘=(V, E')，定義費(fèi)用函數(shù)c為：

然后求解完全圖G'上最大限定花費(fèi)為0的路線即可。

下面來說明當(dāng)且僅當(dāng)圖G'中有一個(gè)費(fèi)用至多為0的回路的時(shí)候，G中才具有一個(gè)哈密頓回路：

  1. 假定圖G中有一個(gè)哈密頓回路h。h中的每條邊都屬于E，因此在G’中的費(fèi)用為0。因此，h在G‘中是費(fèi)用為0的回路。
  2. 反之，假定圖G’中有一個(gè)費(fèi)用h‘至多為0的回路，回路上每條邊的費(fèi)用必為0。因此，h’僅包含E中的邊。
  3. 這樣，我們就得出結(jié)論，h’是圖G中的一個(gè)哈密頓回路。

上述歸約過程在多項(xiàng)式時(shí)間內(nèi)完成，故旅行商問題是NP完全的。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 周一往常在我的腦海里就是黑色的，但是今天好像一切都換了頻道一般，自己愉悅的心情無以言表，雖然得寫值班總結(jié)，但是我竟...
    恩惠有嘉閱讀 385評(píng)論 1贊 2
  • 我
    yun0o0閱讀 114評(píng)論 0贊 0

友情鏈接更多精彩內(nèi)容