1、1第第4 4章章 NP完全性理論完全性理論 解決問題解決問題時時碰到的狀況碰到的狀況 沒沒找到有效率的算法找到有效率的算法 原因原因 我太笨我太笨? 問題本身就太難，不存在有效率的算法可解決問題本身就太難，不存在有效率的算法可解決?231)1) 可滿足問題可滿足問題(SAT)(SAT)2) 圖著色問題圖著色問題3) 作業(yè)調(diào)度問題作業(yè)調(diào)度問題4) 裝箱裝箱問題問題5)5) 背包問題背包問題6) Hamiltonian 回路回路7) TSP(旅行商旅行商)問題問題8) 圖的匹配問題圖的匹配問題9) 頂點覆蓋問題頂點覆蓋問題NP完全問題之范例：41.問題的分類問題的分類 無解的無解的 例如例如：停停

2、機機問題（問題（halting problem） 有解的有解的 簡單的簡單的 多項式時間復(fù)雜度之內(nèi)多項式時間復(fù)雜度之內(nèi):(nk) 困難的困難的 指數(shù)時間復(fù)雜度指數(shù)時間復(fù)雜度:(2n)5指數(shù)時間復(fù)雜度算法的困難度指數(shù)時間復(fù)雜度算法的困難度： 問題描述問題描述 輸入輸入n個元素，其所需花個元素，其所需花費的時間至少是費的時間至少是 (2n) 范例范例 如果如果n=10000，表示要執(zhí)，表示要執(zhí)行行210000個步驟個步驟 這樣的時間數(shù)值是非常大，這樣的時間數(shù)值是非常大，即使使用超級電腦可能也即使使用超級電腦可能也要跑上好幾天才能執(zhí)行完要跑上好幾天才能執(zhí)行完 指數(shù)災(zāi)難：計算量的指數(shù)增長指數(shù)災(zāi)難：計算

3、量的指數(shù)增長6一個問題是簡單或困難的判斷一個問題是簡單或困難的判斷： 往往只有一線之隔，有時往往只有一線之隔，有時用用直覺的方式直覺的方式難以難以判斷判斷 范例范例 在一個加權(quán)圖中，找出頂點在一個加權(quán)圖中，找出頂點x到頂點到頂點y的最短路徑的最短路徑可用可用貪心貪心算法來解決算法來解決 在一個沒有循環(huán)的加權(quán)圖中，找出頂點在一個沒有循環(huán)的加權(quán)圖中，找出頂點x到頂點到頂點y的最的最長路徑長路徑還沒找到有效率之算法還沒找到有效率之算法 判斷問題判斷問題:是或否的問題（是或否的問題（yes-no question） 簡單：是否存在一條從頂點簡單：是否存在一條從頂點x到頂點到頂點y的路徑，使其路的路徑，

4、使其路徑的權(quán)值小于徑的權(quán)值小于M？ 困難困難(？)：“是否存在一條從頂點是否存在一條從頂點x到頂點到頂點y的路徑，使的路徑，使其路徑的權(quán)值大于其路徑的權(quán)值大于M？72. P類：類：屬于屬于P的問題的問題 定義定義:P（deterministic polynomial time） 所有可以被決定型算法（所有可以被決定型算法（deterministic algorithms）在）在多項式時間（多項式時間（polynomial time）內(nèi)解決的問題之集合）內(nèi)解決的問題之集合 決定型（決定型（deterministic） 不管在任何時間點，這個算法在做任何事時，該算法不管在任何時間點，這個算法在做任

5、何事時，該算法的下一步只有一件事可以做的下一步只有一件事可以做 目前我們實際使用的電腦其執(zhí)行模式就是這個樣子，目前我們實際使用的電腦其執(zhí)行模式就是這個樣子，這也是近代計算機科學(xué)最根本的理論基礎(chǔ)這也是近代計算機科學(xué)最根本的理論基礎(chǔ) 范例范例:排序的問題排序的問題 插入排序算法插入排序算法T(n)=O(n2) 有效率的算法即屬于有效率的算法即屬于P 某問題某問題有有n個輸入，該個輸入，該問題問題的處理時間跟的處理時間跟n的多項式成的多項式成比例比例，即存在一個常數(shù)，即存在一個常數(shù)k，對任何，對任何n，T(n)=O(nk)8非決定型非決定型(nondeterministic)的電腦的電腦： 定義定義

6、 當一個算法必須從數(shù)個選項中做選擇，而且它擁有可當一個算法必須從數(shù)個選項中做選擇，而且它擁有可以以“猜猜”中正確的那個選項之能力。中正確的那個選項之能力。 比目前我們實際上所使用的決定型模式之電腦，比目前我們實際上所使用的決定型模式之電腦，還有更強大的功能還有更強大的功能 為了方便接下來的討論，我們可以將非決定型機為了方便接下來的討論，我們可以將非決定型機器上執(zhí)行的算法，想像成它會器上執(zhí)行的算法，想像成它會“同時同時”對每個選對每個選項先項先“猜猜”一個解答，然后再一個解答，然后再“確認確認”這個解答這個解答到底對不對到底對不對 93. NP類：類：屬于屬于NP的問題的問題： 定義定義:NP(

7、nondeterministic polynomial time) 所有可以被非決定型算法（所有可以被非決定型算法（nondeterministic algorithms）在多項式時間內(nèi)解決的問題之集合）在多項式時間內(nèi)解決的問題之集合 如何判斷如何判斷(證明證明)一個問題屬于一個問題屬于NP？ 找到一個多項式時間復(fù)雜度的算法，可以用來找到一個多項式時間復(fù)雜度的算法，可以用來“確認確認”某個問題的選項是否正確即可某個問題的選項是否正確即可 范例：范例： 對于最長路徑對于最長路徑“是或否是或否” 的問題，選擇某一條路徑，的問題，選擇某一條路徑，我們可在多項式時間內(nèi)我們可在多項式時間內(nèi)“確認確認”其

8、值是否大于其值是否大于M104.典型的典型的NP問題問題 問題問題1 圖著色問題圖著色問題 判定問題：是否存在不超過判定問題：是否存在不超過k種顏色的著色方案種顏色的著色方案? 優(yōu)化問題：求圖的最小著色數(shù)和著色方案優(yōu)化問題：求圖的最小著色數(shù)和著色方案 問題問題2 作業(yè)調(diào)度問題作業(yè)調(diào)度問題 判定問題：是否存在代價不超過判定問題：是否存在代價不超過k的作業(yè)調(diào)度的作業(yè)調(diào)度? 優(yōu)化問題：求最小代價調(diào)度優(yōu)化問題：求最小代價調(diào)度11 問題問題3 Bin packing3 Bin packing問題：假設(shè)有問題：假設(shè)有n n種物品，它們種物品，它們的尺寸分別為的尺寸分別為s s1 1, ,s,sn n，0s

9、0si i11另有任意多個箱另有任意多個箱子子(Bins)(Bins)，箱子的容量為，箱子的容量為1 1， 判定問題：任意給定判定問題：任意給定k k，是否存在一種裝箱方，是否存在一種裝箱方法使用的箱子數(shù)法使用的箱子數(shù)k k？ 優(yōu)化問題：求使用最小箱數(shù)的裝箱方法優(yōu)化問題：求使用最小箱數(shù)的裝箱方法12 問題問題4 背包問題背包問題 判定問題：是否存在效益值至少為判定問題：是否存在效益值至少為k的可行子集的可行子集? 優(yōu)化問題：優(yōu)化問題：(見上一章見上一章) 問題問題5 子集和數(shù)問題子集和數(shù)問題s1,s2,sn,C 判定問題：是否存在和數(shù)等于判定問題：是否存在和數(shù)等于C的子集的子集? 優(yōu)化問題：求

10、優(yōu)化問題：求C的最大子集和數(shù)的最大子集和數(shù). 可歸約為背包問題可歸約為背包問題: pi=wi.13 問題問題6 CNF(合取范式合取范式)可滿足問題可滿足問題(SAT) 判定問題：是否存在真假賦值使得該判定問題：是否存在真假賦值使得該CNF為真為真. 合取范式例合取范式例: (x11 x12 x13) (x21 x22 ) (x31 x32 x33) 問題問題7 Hamiltonian 回路回路 判定問題判定問題 問題問題8 TSP(旅行商旅行商)問題問題 判定問題：任意給定一整數(shù)判定問題：任意給定一整數(shù)k，是否存在一長度不超過，是否存在一長度不超過k的的Hamiltonian回路？回路？ 優(yōu)

11、化問題優(yōu)化問題14 問題問題9:頂點覆蓋頂點覆蓋:無向圖中的每一條邊都被某些節(jié)無向圖中的每一條邊都被某些節(jié)點關(guān)聯(lián)點關(guān)聯(lián) 判定問題：給定無向圖判定問題：給定無向圖G和正整數(shù)和正整數(shù)k,是否存在一是否存在一k節(jié)點覆蓋節(jié)點覆蓋. 優(yōu)化問題：最小節(jié)點覆蓋優(yōu)化問題：最小節(jié)點覆蓋 問題問題10: 給定一無向圖給定一無向圖G, k-獨立集獨立集;最大獨立集最大獨立集. 問題問題11: 給定一無向圖給定一無向圖G , k-集團集團;最大集團最大集團. 問題問題10和和11可互相轉(zhuǎn)化可互相轉(zhuǎn)化: 邊互補圖邊互補圖n目標函數(shù)取整數(shù)值時,優(yōu)化值問題和判定問題等價我們可用二分查找從判定問題解得到優(yōu)化值問題的解155.

12、 P與與NP的關(guān)系的關(guān)系 任何一個屬于任何一個屬于P的問題，也一定屬于的問題，也一定屬于NP的問題的問題 是否有是否有某個某個問題是屬于問題是屬于NP，但是不屬于，但是不屬于P呢？呢？ 范例：最長路徑范例：最長路徑“是或否是或否” 的問題的問題 選擇某一條路徑，在多項式時間內(nèi)選擇某一條路徑，在多項式時間內(nèi)“確認確認”其值是否其值是否大于大于M，就是屬于，就是屬于NP 但是到目前為止，仍找不到任何多項式時間的算法來但是到目前為止，仍找不到任何多項式時間的算法來解決它解決它(不屬于不屬于P?) 小結(jié)小結(jié) P屬于屬于NP16“P=NP”的問題的問題? 成立的條件成立的條件 P屬于屬于NP，且，且NP

13、屬于屬于P 目前所知目前所知 可以確認可以確認P屬于屬于NP，但仍無法確認，但仍無法確認NP屬于屬于P 成立的意義成立的意義 如果存在某個有效率的算法可以解決任何一個屬于如果存在某個有效率的算法可以解決任何一個屬于NP的的問題，那就表示真的還有很多有效率的算法沒被發(fā)現(xiàn)問題，那就表示真的還有很多有效率的算法沒被發(fā)現(xiàn) 幾乎沒有人相信幾乎沒有人相信P=NP會成立，而且有會成立，而且有很多人很多人試試著著要反證它（但是也沒成功）要反證它（但是也沒成功）176.NP完全與約化完全與約化 多項式時間約化 NP完全的條件 NP完全的證明NPC(NP Complete)問題，可以這么認為，這種問題，可以這么認

14、為，這種問題只有把解域里面的所有可能都窮舉了之后才問題只有把解域里面的所有可能都窮舉了之后才能得出答案，這樣的問題是能得出答案，這樣的問題是NP里面最難里面最難 。18屬于屬于NP完全的問題完全的問題： 在屬于在屬于NP問題的集合中，有一部問題的集合中，有一部分分為為NP完全問題完全問題（NP-complete，NPC），其狀態(tài)到目前為止還是），其狀態(tài)到目前為止還是未知的。未知的。 NP完全問題完全問題有可能屬于有可能屬于P，也有可能不屬于，也有可能不屬于P，也，也就是說，這些問題可以很容易地以非決定性機器來就是說，這些問題可以很容易地以非決定性機器來解決，但是還沒有人找到在傳統(tǒng)機器（決定型機

15、器）解決，但是還沒有人找到在傳統(tǒng)機器（決定型機器）上可以有效地解決這些問題的方法上可以有效地解決這些問題的方法 NP完全問題在某一個意義上，是完全問題在某一個意義上，是NP內(nèi)最難的問題內(nèi)最難的問題 想要證明某些問題是屬于想要證明某些問題是屬于NP完全的主要方式：完全的主要方式： 多項式時間約化（多項式時間約化（reducibility） 19多項式時間約化（多項式時間約化（reducibility）： 概念概念一個問題一個問題L可以約化成另外一個問題可以約化成另外一個問題L，如果，如果L的任何實例（的任何實例（instance）都可以）都可以多項式時間內(nèi)多項式時間內(nèi)轉(zhuǎn)化轉(zhuǎn)化成成L的一個實例，則

16、它的解答也提供一個的一個實例，則它的解答也提供一個解答給解答給L的實例的實例 范例范例在一個未決定的在一個未決定的x上解決線性方程式的問題，上解決線性方程式的問題，并將其約化成決定二次方程式的問題并將其約化成決定二次方程式的問題例如：對一個實例例如：對一個實例ax+b=0，我們將它轉(zhuǎn)化成，我們將它轉(zhuǎn)化成0 x2+ax+b=0，其解答提供一個解答給，其解答提供一個解答給ax+b=020 意義意義 如果一個問題如果一個問題L可約化成另一個問題可約化成另一個問題L，則則L在某個意義上與在某個意義上與L相比是相比是“不會更難解決不會更難解決” 問題問題L約化成約化成L后，當解決問題后，當解決問題L時，

17、我們時，我們可以使用可以使用L的的“容易性容易性”來證明來證明L的的“容易容易性性” 21多項式時間約化的數(shù)學(xué)表示多項式時間約化的數(shù)學(xué)表示： 我們說一個問題我們說一個問題L1能夠在多項式時間約化到一個能夠在多項式時間約化到一個問題問題L2，可寫成，可寫成L1 p L2：如果存在一個多項式時：如果存在一個多項式時間可以計算完成的函數(shù)間可以計算完成的函數(shù) f ，并讓所有的輸入，并讓所有的輸入 x，使，使得：得： xL1當且僅當當且僅當 f (x) L2 我們稱函數(shù)我們稱函數(shù) f 為約化函數(shù)，而計算為約化函數(shù)，而計算 f 的一個多項式的一個多項式時間算法時間算法F則稱為約化算法。則稱為約化算法。 2

18、2約化函數(shù)約化函數(shù) f 產(chǎn)生的對應(yīng)示意圖產(chǎn)生的對應(yīng)示意圖 f23 定理定理1：如果如果問題問題L1、L2滿足滿足L1 p L2，L2屬于屬于P 類類則則L1屬于屬于P類類 證明：參閱下圖證明：參閱下圖 由于由于L2是屬于是屬于P類類，可令，可令A(yù)2是決定是決定L2的多項式時間算法的多項式時間算法 A1是使用是使用F來決定來決定“對于任何輸入對于任何輸入x，x 屬于屬于L1是否成是否成立立”的算法的算法 首先將任何輸入首先將任何輸入x在多項式時間內(nèi)轉(zhuǎn)換到在多項式時間內(nèi)轉(zhuǎn)換到f(x)，然后，然后使用使用A2來決定來決定f(x)屬于屬于L2是否成立，若成立則表示是否成立，若成立則表示x屬于屬于L1也

19、成立，反之則不成立也成立，反之則不成立 因為因為F和和A2都是多項式時間算法，而都是多項式時間算法，而f(x)屬于屬于L2是否成是否成立則可得到立則可得到x屬于屬于L1是否成立，其也在多項式時間內(nèi)完是否成立，其也在多項式時間內(nèi)完成，所以成，所以A1也是多項式時間算法，即也是多項式時間算法，即L1屬于屬于P類類成立成立 24約化算法示意圖約化算法示意圖25NP完全的條件完全的條件：多項式時間約化多項式時間約化 如果如果L1 p L2，則，則L1在一個多項式因子在一個多項式因子內(nèi)內(nèi)不會比不會比L2困難困難 NP完全問題的定義：一個問題完全問題的定義：一個問題L是是NP完全的條件為完全的條件為 L屬

20、于屬于NP，而且，而且 對每個屬于對每個屬于NP的的L，具有，具有L p L的性的性質(zhì)質(zhì)NP困難（困難（NP-hard） 只要滿足第只要滿足第2個條件即符合個條件即符合所有所有NP的問題都不會的問題都不會比這類問題還困難，也就是比這類問題還困難，也就是NP問題中最困難的問題中最困難的部份也包含在這類問題之內(nèi)部份也包含在這類問題之內(nèi) NP完全問題也就是完全問題也就是NP問題內(nèi)最難的集合問題內(nèi)最難的集合 26 定理定理2：如果任何如果任何NP完全問題是多項式時間完全問題是多項式時間可以解決的，則可以解決的，則P=NP。 同樣的，如果同樣的，如果NP內(nèi)的任何問題都不是多項內(nèi)的任何問題都不是多項式時間

21、可以解決，則沒有任何式時間可以解決，則沒有任何NP完全問題完全問題是多項式時間可以解決是多項式時間可以解決 27PNP (?) 定理定理2就是為什么就是為什么PNP問題的研究是以問題的研究是以NP完全性完全性問題為重心的理由，而目前大部分的理論計算機問題為重心的理由，而目前大部分的理論計算機學(xué)者相信學(xué)者相信PNP 有人可能會找到一個多項式時間的算法，來證明有人可能會找到一個多項式時間的算法，來證明P=NP 不過既然還沒發(fā)現(xiàn)任何不過既然還沒發(fā)現(xiàn)任何NP完全問題的多項式算法，完全問題的多項式算法，那么一個問題是屬于那么一個問題是屬于NP完全的證明，就是說明此完全的證明，就是說明此問題不易處理的最佳

22、證據(jù)問題不易處理的最佳證據(jù) 28目前對目前對P、NP、NP完全問題之完全問題之間間關(guān)系的認知關(guān)系的認知 29 定理定理3：若：若L使使某個某個屬于屬于NP完全的完全的L，滿足滿足L p L，則則L屬于屬于NP困難困難(NP-Hard)。如果。如果L同時也屬于同時也屬于NP，則則L屬于屬于NP完全完全 證明證明 如果有某個已知的問題如果有某個已知的問題L是屬于是屬于NP完全，則對于所有屬于完全，則對于所有屬于NP的的L，我們有，我們有L p L，也就是所有屬于，也就是所有屬于NP的問題都的問題都可以在多項式時間內(nèi)約化成問題可以在多項式時間內(nèi)約化成問題L。 若有某個問題若有某個問題L，具有，具有L

23、 p L，則所有屬于，則所有屬于NP的問題在多的問題在多項式時間內(nèi)約化成項式時間內(nèi)約化成L后，再用一個多項式時間算法約化成后，再用一個多項式時間算法約化成L，也就是所有屬于，也就是所有屬于NP的問題都可以在多項式時間內(nèi)約化的問題都可以在多項式時間內(nèi)約化成問題成問題L，即，即L p L，此表示，此表示L是是NP困難。困難。 再加上如果再加上如果L也屬于也屬于NP，則依照，則依照NP完全的條件，完全的條件，L也是屬也是屬于于NP完全完全 。30 問題問題L是是NP-困難困難問題，如果：問題，如果： 每個每個NP問題都可多項式地約化為問題問題都可多項式地約化為問題 L. 問題問題 L 是是 NP-完

24、全問題完全問題. 如果如果: 它是它是NP問題問題, 同時它還是同時它還是NP-困難困難問題問題. NP-完全問題的性質(zhì)完全問題的性質(zhì) 所有所有NP-完全問題完全問題,相對于多項式約化關(guān)系相對于多項式約化關(guān)系,是自是自反反,對稱對稱,傳遞的傳遞的,即構(gòu)成一個閉類即構(gòu)成一個閉類. 如果能找到一個如果能找到一個NP完全問題的多項式算法則完全問題的多項式算法則P=NP 有有NP-困難困難問題但不知它是否在問題但不知它是否在NP類內(nèi)類內(nèi)(第第kth重子集問題重子集問題)31NP完全的證明完全的證明：依照定理依照定理3，我們可以用我們可以用以以下的步驟來證明某個下的步驟來證明某個新的問題新的問題L屬于屬

25、于NP完全完全證明證明L屬于屬于NP描述一個算法描述一個算法F，可以將某個已知屬于，可以將某個已知屬于NP完完全問題的全問題的L約化成約化成L證明算法證明算法F是在多項式時間復(fù)雜度內(nèi)完成是在多項式時間復(fù)雜度內(nèi)完成 32第一個第一個NP完全的問題完全的問題 ： 約化的機制可以用某個約化的機制可以用某個NP完全的問題來證明另一完全的問題來證明另一個問題也是屬于個問題也是屬于NP完全的問題完全的問題 第一個被證明是屬于第一個被證明是屬于NP完全的問題是那個？完全的問題是那個？ S. A. Cook先生在先生在1971年完成直接證明滿足性年完成直接證明滿足性問題（問題（SAT）是屬于）是屬于NP完全完

26、全 證明之關(guān)鍵證明之關(guān)鍵 具有非決定型運算能力的具有非決定型運算能力的Turing Machine33NP完全問題完全問題證明的證明的范例范例： 3-CNF滿足性問題（滿足性問題（3-CNF-SAT） 匹配問題（匹配問題（CLIQUE） 頂點覆蓋問題（頂點覆蓋問題（VERTEX-COVER） 34證明證明NP完全問題的族系關(guān)系完全問題的族系關(guān)系353-CNF-SAT： CNF(合取范式合取范式)可滿足問題可滿足問題(SAT) 如果每個括弧內(nèi)的式子剛好有三個不同的變?nèi)绻總€括弧內(nèi)的式子剛好有三個不同的變量量，則，則這個邏輯方程式屬于這個邏輯方程式屬于3-CNF 范例范例:(x1-x2 x3) (

27、x1 x2 x4 ) (-x3 x2 -x4) 問題問題 一組指定變量的值，是否可使某個一組指定變量的值，是否可使某個3-CNF方程式方程式為為“真真”，即能滿足此方程式，即能滿足此方程式 36 3-CNF-SAT屬于屬于NP完全完全 證明：證明： 選定一選定一組變量的值并代入組變量的值并代入3-CNF方程式中，由方程式中，由于只需要在多項式時間內(nèi)就可以確認會使方程于只需要在多項式時間內(nèi)就可以確認會使方程式的值為式的值為“真真”或或“假假”，因此，因此3-CNF-SAT屬屬于于NP。 接著接著我們只要利用已知屬于我們只要利用已知屬于NP完全的完全的SAT問題，問題，來來證明證明SAT p 3-

28、CNF-SAT即可即可 37SAT p 3-CNF-SAT 之證明之證明： SAT的方程式的方程式DNFCNF(DeMorgan定律定律) 范例范例：x1- x2x3-x4x5x4x1 (-x3x2 )x5 (x1- x2 x3-x4x5 ) (x4 )(x1 -x3x5)(x1x2x5 ) (-x1x2-x3 x4 -x5 )(-x4 )(-x1x3-x5) (-x1-x2-x5) 38 如果如果變量的數(shù)目剛好是三個，則不需改變變量的數(shù)目剛好是三個，則不需改變 如果如果變量不足三個，則加入額外的變量湊足三個變量不足三個，則加入額外的變量湊足三個來取代來取代 例如例如(x4)=(x4 y1 y

29、2) 其中其中y1、y2的值都為的值都為0，因為任何變量加，因為任何變量加0其值其值不變，所以其結(jié)果跟原先括弧內(nèi)的結(jié)果一致不變，所以其結(jié)果跟原先括弧內(nèi)的結(jié)果一致。 39 范例范例 當變量超過三個時當變量超過三個時，通過附加，通過附加加入額外的變量加入額外的變量分解分解為多三個為多三個變量變量項項 如果原括弧是滿足的，表示其內(nèi)的變量至少有一個為如果原括弧是滿足的，表示其內(nèi)的變量至少有一個為1，假設(shè)，假設(shè)xi=1，則將更改后的式子中其，則將更改后的式子中其y1，y2，.，yi-2設(shè)為設(shè)為1，其余為，其余為0，那更改后的式子也會滿足那更改后的式子也會滿足 如果更改后的式子是滿足的，因為沒有任何值可使

30、如果更改后的式子是滿足的，因為沒有任何值可使 為為1，則則x1，x2，.，xk之中至少有一個為之中至少有一個為1，所以原式子也會，所以原式子也會滿足滿足。(x1x2x3 xk ) (x1x2y1)(x3-y1y2)(x4-y2y3)(xk-1xk-yk-3)(y1)(-y1y2)(-y2y3)( -yk-3)403-CNF-SAT屬于屬于NP完全之證明完全之證明： 如此，方程式就成了如此，方程式就成了3-CNF形式，而且任何一組形式，而且任何一組變量變量xi的值可以讓的值可以讓SAT和和3-CNF-SAT得到相同的得到相同的答案。答案。 上上述的轉(zhuǎn)換是利用方程式分析樹（述的轉(zhuǎn)換是利用方程式分析

31、樹（parse tree）的）的建立、變更、和搜索來完成，其都是多項式時間建立、變更、和搜索來完成，其都是多項式時間內(nèi)就可完成內(nèi)就可完成。 因此因此SAT p 3-CNF-SAT，再加上，再加上3-CNF-SAT屬屬于于NP，故得證，故得證3-CNF-SAT也是屬于也是屬于NP完全完全 41圖的匹配圖的匹配問題屬于問題屬于NP完全完全的的證明證明： 匹配匹配 無向圖無向圖G=(V，E)中的一個匹配是頂點中的一個匹配是頂點V的一個子的一個子集合集合V，即，即V包含包含V，使得在，使得在V內(nèi)的每一對頂點內(nèi)的每一對頂點都是由都是由E內(nèi)的一內(nèi)的一條條邊邊相關(guān)聯(lián)相關(guān)聯(lián) 一個匹配是一個匹配是G的一個完整子

32、圖形的一個完整子圖形 一個匹配的一個匹配的“大小大小”是指它包含的頂點數(shù)目是指它包含的頂點數(shù)目 匹配問題是指在一個圖形中找出有最大大小的一個匹配問題是指在一個圖形中找出有最大大小的一個匹配匹配，其最其最優(yōu)優(yōu)化問題?；瘑栴}。而其判定問題而其判定問題就是一個指定就是一個指定大小大小k的匹配是否存在圖中，其可定義為：的匹配是否存在圖中，其可定義為： CLIQUE=(G，k)：G是有大小為是有大小為k的一個匹配的圖的一個匹配的圖 42 匹配問題（匹配問題（CLIQUE）屬于）屬于NP完全。完全。 證明證明： 檢驗檢驗V是不是一個匹配，可以檢查每一對邊是不是一個匹配，可以檢查每一對邊(u，v)是否屬于是

33、否屬于E，這些檢查可以在多項式時間內(nèi)，這些檢查可以在多項式時間內(nèi)完成，即完成，即CLIQUE屬于屬于NP。 證明證明3-CNF-SAT p CLIQUE，CLIQUE屬于屬于NP困難困難。 433-CNF-SAT p CLIQUE之證明之證明： 關(guān)聯(lián)關(guān)聯(lián)方程式和圖形方程式和圖形 以以3-CNF方程式的每個括弧為一組，括弧內(nèi)的方程式的每個括弧為一組，括弧內(nèi)的三個變量都設(shè)定為一個頂點三個變量都設(shè)定為一個頂點 這些頂點即為圖形這些頂點即為圖形G的頂點的頂點V，而在這個圖形，而在這個圖形G中的邊中的邊E是指每個頂點跟所有其它的頂點相連是指每個頂點跟所有其它的頂點相連接的邊，但是接的邊，但是以以下兩下兩

34、種情況種情況除外：除外： 不跟屬于同括弧的頂點連接不跟屬于同括弧的頂點連接 每個相對于變量每個相對于變量xi的頂點，不跟的頂點，不跟其自已的補其自已的補變量的頂點連接變量的頂點連接44范例范例：從從3-CNF轉(zhuǎn)換的圖形轉(zhuǎn)換的圖形(x1-x2 x3) (x1 x2 x4 )x1-x2x1x2x3x4(x1-x2x3)(x1x2x4 )45 任何一組可以滿足任何一組可以滿足3-CNF方程式的變量，一定會讓每個括弧內(nèi)方程式的變量，一定會讓每個括弧內(nèi)的三個變量至少其中一個為的三個變量至少其中一個為1，而從每個括弧內(nèi)挑選被設(shè)為，而從每個括弧內(nèi)挑選被設(shè)為1的的變量其相對應(yīng)的頂點，這些頂點所成的集合變量其相

35、對應(yīng)的頂點，這些頂點所成的集合V，其數(shù)目為，其數(shù)目為k，這就是圖形這就是圖形G的一個匹配。對于屬于的一個匹配。對于屬于V的任兩個頂點的任兩個頂點u、v而言，而言，其一定不會對應(yīng)到相同的括弧，而且兩者對應(yīng)的變量互不為補其一定不會對應(yīng)到相同的括弧，而且兩者對應(yīng)的變量互不為補數(shù)，所以邊數(shù)，所以邊(u，v)一定屬于一定屬于E。 若若G有一個大小為有一個大小為k的匹配的匹配V，因為，因為G內(nèi)的邊，沒有一對是由對內(nèi)的邊，沒有一對是由對應(yīng)到相同括弧的頂點連接而成，所以每個括弧對應(yīng)的頂點至少應(yīng)到相同括弧的頂點連接而成，所以每個括弧對應(yīng)的頂點至少有一個會屬于有一個會屬于V?？蓪⒚總€屬于?？蓪⒚總€屬于V頂點其相對

36、應(yīng)的變量設(shè)為頂點其相對應(yīng)的變量設(shè)為1，并可以排除某個變量和它的補數(shù)同時被設(shè)成并可以排除某個變量和它的補數(shù)同時被設(shè)成1，所以每個括弧都，所以每個括弧都可以滿足，而整個可以滿足，而整個3-CNF方程式也可滿足。也就是可以滿足方程式也可滿足。也就是可以滿足3-CNF方程式的變量中有方程式的變量中有k個值為個值為1，其代表相對應(yīng)的圖形有大小，其代表相對應(yīng)的圖形有大小為為k的匹配，兩者有相對應(yīng)的解答。的匹配，兩者有相對應(yīng)的解答。 因此因此CLIQUE也是屬于也是屬于NP完全。完全。 46頂點覆蓋問題屬于頂點覆蓋問題屬于NP完全完全的的證明證明： 頂點覆蓋頂點覆蓋 無向圖無向圖G=(V，E)的一個頂點覆蓋

37、是頂點的一個頂點覆蓋是頂點V的一個子集合的一個子集合V ，即，即V包含包含V ，使得：如果邊，使得：如果邊(u,v)屬于屬于E ，則，則u屬于屬于V或或v屬于屬于V 每個頂點每個頂點“覆蓋覆蓋”它的投射邊，而它的投射邊，而G的一個頂點覆蓋是頂?shù)囊粋€頂點覆蓋是頂點的一個集合，其覆蓋點的一個集合，其覆蓋E內(nèi)的所有邊。而一個頂點覆蓋的內(nèi)的所有邊。而一個頂點覆蓋的大小為它里面的頂點數(shù)目。大小為它里面的頂點數(shù)目。 頂點覆蓋問題頂點覆蓋問題 要在一個圖形中找出有最小大小的一個頂點覆蓋要在一個圖形中找出有最小大小的一個頂點覆蓋 以是或否的問題來看，就是一個圖形中是否有一個指定大以是或否的問題來看，就是一個圖

38、形中是否有一個指定大小小k的一個頂點覆蓋，其可定義為：的一個頂點覆蓋，其可定義為：VERTEX-COVER=(G，k)：G是有大小為是有大小為k的一個頂點覆蓋的一個頂點覆蓋47 頂點覆蓋問題頂點覆蓋問題(VERTEX-COVER)屬于屬于NP完全。完全。 證明證明： 確定確定V的數(shù)目為的數(shù)目為k，然后對每個邊，然后對每個邊(u,v)屬于屬于E，檢查檢查u屬于屬于V或或v屬于屬于V，這些檢查的可以在多這些檢查的可以在多項式時間內(nèi)完成，即頂點覆蓋屬于項式時間內(nèi)完成，即頂點覆蓋屬于NP 接著接著證明證明CLIQUE p VERTEX-COVER，得，得VERTEX-COVER屬于屬于NP困難困難。4

39、8CLIQUE p VERTEX-COVER的的證明證明： 定義無向圖定義無向圖G=(V，E)的補的補圖圖 即為頂點即為頂點V 所組成的完整圖形，其再扣掉所組成的完整圖形，其再扣掉G 包含的邊包含的邊E 所所成的圖形成的圖形 范例范例 下圖的下圖的 (a)、(b)互為補數(shù)互為補數(shù) 對于匹配問題的一個實例對于匹配問題的一個實例(G，k)，我們可以很容易地，我們可以很容易地在多項式時間內(nèi)建在多項式時間內(nèi)建構(gòu)構(gòu)出出G的補數(shù)，而約化算法的輸出的補數(shù)，而約化算法的輸出為頂點覆蓋的實例為頂點覆蓋的實例( ，|V|-k)，其中，其中|V|表示頂點表示頂點V的的數(shù)目。要完成這個證明，等于要我們證明：數(shù)目。要完

40、成這個證明，等于要我們證明： 圖形圖形G有一個大小為有一個大小為k的匹配的匹配，當，當且且僅當僅當， 有一個大小為有一個大小為|V|-k的頂點覆蓋的頂點覆蓋。G(V, E )GG49從匹配問題約化成頂點覆蓋問題之范例從匹配問題約化成頂點覆蓋問題之范例 507.如何處理如何處理NP完全問題完全問題 第一個第一個NP完全問題（完全問題（Cook定理定理 1971） 可滿足性問題是可滿足性問題是NP完全問題完全問題 六個六個NP完全問題（完全問題（Karp 1972) 3SAT，3DM，VC，團，團，HC，劃分，劃分 更多的更多的NP完全問題完全問題 1979年：年：300多個多個 1998年：年：

41、2000多個多個 實際的問題不會消失實際的問題不會消失51 掃雷是掃雷是NP完全問題完全問題 結(jié)果于結(jié)果于2000年發(fā)表在年發(fā)表在Mathematical Intelligencer上，論文題目上，論文題目是是Minesweeper is NP-complete，這里有作者的簡單的問題和，這里有作者的簡單的問題和證明介紹。證明方法是證明掃雷問題可以編碼任何邏輯電路，證明介紹。證明方法是證明掃雷問題可以編碼任何邏輯電路，包括包括NP-hard的的3SAT問題。作者還有一個非常直觀的問題。作者還有一個非常直觀的PPT演示演示證明過程。證明過程。 空當接龍是空當接龍是NP完全問題完全問題 論文：論文

42、：Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence Journal 143(2):219-262, 2003. 蜘蛛紙牌是蜘蛛紙牌是NP完全問題完全問題 論文：論文：Springer Berlin, Heidelberg, The Complexity of Solitaire, Mathematical Foundations of Computer Science 2007: 182-193, 2007 Windows自帶的游戲都是自帶的游戲都是NP完全問題完全問題52（1）并行計算）并行計算 以硬件設(shè)備換取時間以硬件設(shè)備換取時間 存在著很多種并行計算模型存在著很多種并行計算模型 理想模型理想模型PRAM可多項式時間解可多項式時間解NP完全問題完全問題 實際中效果不