1、算法復(fù)雜性與NPC問(wèn)題問(wèn)題與算法的描述 圖靈機(jī)與確定性算法 NP類問(wèn)題 NP完全問(wèn)題 證明問(wèn)題為NP完全的方法 NP困難問(wèn)題 P、NP、co-NP的思考 問(wèn)題與算法的描述 問(wèn)題問(wèn)題(problem)：有待回答、通常含有幾個(gè)取值還未確定的自由變量的一般性提問(wèn)(question)。 表示符號(hào)： 問(wèn)題的構(gòu)成問(wèn)題的構(gòu)成： 1)對(duì)其關(guān)于參數(shù)的一般性描述； 2)對(duì)該問(wèn)題的答案所應(yīng)滿足的某些特性的說(shuō)明。 問(wèn)題的實(shí)例問(wèn)題的實(shí)例：指定問(wèn)題中所有參數(shù)的具體取值 。表示符號(hào)： 旅行商問(wèn)題： 參數(shù)描述：n個(gè)城市C1,C2,Cn，城市間距離d(Ci,Cj) 答案描述：城市的排序：C(1) , C(2) , C(n) ，

2、最小化目標(biāo)值: 1in-1 d(C(i) , C(i+1) ) + d(C(n) , C(1) ) 旅行商問(wèn)題實(shí)例: n=4, C1 , C2 , C3 , C4 , d(C1,C2)=10, d(C1,C3)=5, d(C1,C4)=9, d(C2,C3)=6, d(C2,C4)=9, d(C3,C4)=3 答案：C1, C3, C4,C2, 長(zhǎng)度: 27判定問(wèn)題及描述 判定問(wèn)題：答案只有“是”與“非”兩種可能的問(wèn)題。 實(shí)例集合D，回答為“是”的集合 Y 描述方法：分成兩個(gè)部分 例例：用諸如集合、圖、函數(shù)等各種描述分量來(lái)刻畫(huà)判定問(wèn)題的一般性例子; 問(wèn)問(wèn)：陳述基于一般性例子所提出的一個(gè)“是非”

3、提問(wèn)。 旅行商問(wèn)題： 例例 待訪問(wèn)城市的有限集合C=C1,C2,Cn、每對(duì)城市之間的距離 d(Ci,Cj)Z+ 以及一個(gè)界 BZ+ 。 問(wèn)問(wèn) 在C中存在一個(gè)總長(zhǎng)不超過(guò)B的、通過(guò)所有城市的旅行路線嗎？即是否存在的一個(gè)排序：C(1) , C(2) , C(n) ，使得 1in-1 d(C(i) , C(i+1) ) + d(C(n) , C(1) ) B 算法算法(algorithm)是指用來(lái)求解某一問(wèn)題的、帶有一般性的一步一步的過(guò)程。是計(jì)算流程的抽象形式，超越實(shí)現(xiàn)細(xì)節(jié)。 問(wèn)題和語(yǔ)言 算法的性能的合理刻劃：計(jì)算模型、問(wèn)題實(shí)例的規(guī)模 計(jì)算模型：圖靈機(jī)（TM）、隨機(jī)存儲(chǔ)機(jī)（RAM）等； 問(wèn)題實(shí)例的規(guī)模

4、：描述或表示它所需要的信息量。 編碼策略：從某一字符集中選取所需字符構(gòu)成有限長(zhǎng)字符串。合理的編碼策略具有可解碼性、簡(jiǎn)潔性，常利用結(jié)構(gòu)化字符串，通過(guò)遞歸、復(fù)合等方式給出。對(duì)于問(wèn)題實(shí)例 I，在一個(gè)合理的編碼策略 e 下，描述該實(shí)例的字符串中的字符個(gè)數(shù)稱為該問(wèn)題的輸入長(zhǎng)度，也作為該問(wèn)題實(shí)例的輸入規(guī)模。 旅行商問(wèn)題的一個(gè)實(shí)例：字符集C,/,0,1,2,3,4,5,6,7,8,9，編碼字符串：C1C2C3C4/10/5/9/6/9/3 ，輸入長(zhǎng)度為32。 長(zhǎng)度多項(xiàng)式相關(guān)：LengthIp(|x|) 且 |x|q(LengthI) 語(yǔ)言：字符集中字符組成的一些有限長(zhǎng)字符串的集合L * L,e=x*|x為某

5、個(gè)例子IY在 e 下的編碼圖靈機(jī)的構(gòu)成 圖靈機(jī)圖靈機(jī)：一個(gè)具有存儲(chǔ)載體的、按照具體指令可完成向左或向右移動(dòng)、放置標(biāo)記、抹去標(biāo)記以及在計(jì)算終止時(shí)停機(jī)等四種基本操作的虛擬機(jī)器，可以看作是描述算法的語(yǔ)言。 確定性單帶圖靈機(jī)確定性單帶圖靈機(jī)( DTM )的組成的組成：一個(gè)有限狀態(tài)控制器、一個(gè)讀寫(xiě)頭、一條雙向的具有無(wú)限多個(gè)格的線性帶。 DTM程序規(guī)定如下信息程序規(guī)定如下信息： 1. 字符取用集，其包含輸入字符集及空白符b 。 2. 一個(gè)有限狀態(tài)集Q，包含初始狀態(tài)q0和兩個(gè)停機(jī)狀態(tài)qY，qN 3. 一個(gè)轉(zhuǎn)移函數(shù)：(QqY , qN) Q l, r有限狀態(tài)控制器 -5 -4 -3 -2 -1 0 1 2 3

6、 4 5 6 7 8 讀寫(xiě)頭確定性算法 圖靈機(jī)程序的運(yùn)行圖靈機(jī)程序的運(yùn)行：將輸入字符串x一格一個(gè)字符地存放在帶格1到帶格|x|中，所有其它的帶格均存放空白字符 b。讀寫(xiě)頭位于帶格1，狀態(tài)控制器處于初始狀態(tài)，即開(kāi)始按轉(zhuǎn)移函數(shù)指令一步一步地運(yùn)行：若當(dāng)前狀態(tài)q是停止?fàn)顟B(tài)qY或qN，則停止，并分別回答“是”或“非”。若當(dāng)前狀態(tài)q既不是qY也不是qN，則按照轉(zhuǎn)移函數(shù) (q , s) = (q, s, )讀寫(xiě)頭首先擦掉當(dāng)前帶格的字符s，并寫(xiě)上字符s,然后依照=l或 r 將讀寫(xiě)頭向左或右移動(dòng)一格，最后將當(dāng)前狀態(tài)q更新為q 。 圖靈機(jī)程序M所識(shí)別的語(yǔ)言： LM=x*|M作用于x時(shí)，停機(jī)于狀態(tài)qY 算法算法：當(dāng)

7、一個(gè)DTM程序?qū)Χx于其輸入字符集上的所有可能字符串均（在有限步內(nèi)）停機(jī)時(shí)，稱其為一個(gè)算法。 DTM程序M求解問(wèn)題：M是算法，且 LML( , e )。復(fù)雜性函數(shù)定義 一個(gè)DTM程序M對(duì)于輸入 x 的計(jì)算時(shí)間定義為該程序從開(kāi)始直至進(jìn)入停機(jī)狀態(tài)為止所運(yùn)行的步數(shù)。 DTM程序M的時(shí)間復(fù)雜性函數(shù)定義：TM: Z+ Z+ TM(n)=maxm|存在x*，|x|=n，使得M對(duì)x的計(jì)算時(shí)間為 m 多項(xiàng)式時(shí)間DTM程序：存在多項(xiàng)式 p(x) ，使得 TM(n) p(n) P-語(yǔ)言類： P=L|存在多項(xiàng)式時(shí)間程序M，使得L=LM 多項(xiàng)式問(wèn)題 : 存在多項(xiàng)式時(shí)間DTM程序M，其在編碼策略e下求解，即 L (,e

8、)P。稱為P-類問(wèn)題。 P-類語(yǔ)言只能描述具有多項(xiàng)式時(shí)間確定算法的問(wèn)題。非確定性單帶圖靈機(jī) 非確定性圖靈機(jī)包括多值模型、猜想模塊模型 多值模型規(guī)定如下信息： 1. 字符取用集，其包含輸入字符集及空白符b 。 2. 一個(gè)有限狀態(tài)集Q，包括初始狀態(tài)q0和兩個(gè)停機(jī)狀態(tài)qY，qN 3. 一個(gè)多值轉(zhuǎn)移函數(shù)：(QqY , qN) 2 Q l, r (q , s ) = S Q l, r 非確定性圖靈機(jī)可以被想象為在同一時(shí)刻能夠獨(dú)立、并行地完成多種運(yùn)算（表現(xiàn)在轉(zhuǎn)移函數(shù)的多值性）。 猜想模塊模型：加一個(gè)猜想模塊猜想模塊有限狀態(tài)控制器 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 猜想頭讀寫(xiě)

9、頭多值性模型與確定性模型示意 拒絕接受非確定型計(jì)算接受或拒絕確定型計(jì)算猜想模塊模型 猜想模塊有一個(gè)只進(jìn)行寫(xiě)操作的猜想頭； 計(jì)算進(jìn)程分為兩個(gè)階段：猜想階段和驗(yàn)證階段 首先，輸入字符串x被寫(xiě)在從1到|x|的帶格中，其余為空白符。猜想頭位于帶格-1處，有限狀態(tài)控制器的讀寫(xiě)頭處于帶格1的位置，有限狀態(tài)控制器處于不起作用狀態(tài)。 其次，猜想模塊處于起作用狀態(tài)，一次一步地指示猜想頭：要么在被掃描的帶格中寫(xiě)下中的一個(gè)字符,并向左移動(dòng)一格；要么停止 猜想模塊停止，有限狀態(tài)控制器即開(kāi)始起作用，它首先處于初始狀態(tài)q0，然后就按照DTM完全相同的規(guī)則進(jìn)行。這是檢驗(yàn)階段，由猜想頭寫(xiě)出的字符串也被考慮。停機(jī)qY，稱為可接

10、受的計(jì)算。 對(duì)于一個(gè)給定的輸入字符串x，NDTM程序M將會(huì)做無(wú)限多個(gè)可能的計(jì)算。如果這些計(jì)算中至少有一個(gè)為可接受的計(jì)算，則稱NDTM程序M接受字符串 x。 LM=x | 程序M接受xM所識(shí)別的語(yǔ)言NDTM的時(shí)間復(fù)雜性函數(shù) 程序NDTM接受x的時(shí)間：在M對(duì)于x的所有可接受計(jì)算中，程序從一開(kāi)始直到停機(jī)狀態(tài)為止在猜想和檢驗(yàn)階段所進(jìn)行的步數(shù)的最小值 。 NDTM程序M時(shí)間復(fù)雜性函數(shù)定義：TM: Z+ Z+ TM(n)=maxm | 存在xLM，|x|=n， 使得M接受x所需的計(jì)算時(shí)間為 m 多項(xiàng)式時(shí)間NDTM程序M：存在多項(xiàng)式p(x)，使得TM(n)p(n)。 NP語(yǔ)言類：NP=L|存在多項(xiàng)式時(shí)間ND

11、TM程序M，使L=LM NP類問(wèn)題：存在合理編碼策略e，使得L,eNP。 任何現(xiàn)有的計(jì)算模型都可以通過(guò)加上一個(gè)類似于NDTM中的帶有只寫(xiě)頭的猜想模塊來(lái)擴(kuò)充，而且所有如此得到的計(jì)算模型在多項(xiàng)式時(shí)間內(nèi)可相互轉(zhuǎn)換的意義下將是等價(jià)的。沒(méi)有必要特別提及NDTM模型，將簡(jiǎn)單地說(shuō)“多項(xiàng)式時(shí)間不確定算法多項(xiàng)式時(shí)間不確定算法”，并將NP類語(yǔ)言與所有可用多項(xiàng)式時(shí)間不確定算法求解的判定問(wèn)題等同看待。 無(wú)向圖的團(tuán)問(wèn)題 問(wèn)題描述：例例：給定一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖G=(V,E)及整數(shù) k問(wèn)問(wèn)：G是否包含一個(gè)具有k個(gè)頂點(diǎn)的完全子圖（團(tuán)）？ 問(wèn)題實(shí)例的字符串表示：G鄰接矩陣，長(zhǎng)度：m=n2+logk +1 CLIQUE=w#

12、v | w, v0,1*，以w為鄰接矩陣的圖G有 一個(gè)k頂點(diǎn)的團(tuán)，v是k的二進(jìn)制表示 非確定性算法設(shè)計(jì)第一階段：將輸入字符串w#v進(jìn)行分解，計(jì)算n=|w|1/2以及用v表 示的整數(shù)k。若輸入不具有形式w#v或|w|不是平方數(shù)，則拒絕。第二階段：非確定性選擇V的一個(gè)k元子集V ,并用其集合特征向 量表示A1.n。第三階段：確定性地檢查V的團(tuán)性質(zhì)。若V是一個(gè)團(tuán)則接受， 否則拒絕。團(tuán)問(wèn)題選擇子集的非確定性算法 integer j,m; j:=0; for i to n do m:=choice(0,1); case: m=0: Ai:=0; m=1: Ai:=1; j:=j+1; endcase e

13、ndfor if jk then failure; endif 第一階段可在O(n2)內(nèi)完成。第二階段可在O(n)內(nèi)完成；第三階段可在O(k2)內(nèi)完成?？偟臅r(shí)間復(fù)雜度為 O(n2+k2)定理：對(duì)于每一個(gè)NP問(wèn)題，都存在多項(xiàng)式 p ( x ) 使 得 問(wèn) 題 可 以 用 一 個(gè) 時(shí) 間 復(fù) 雜 度為O(2p(n)的確定性算法求解 證明證明：設(shè)A為求解的一個(gè)多項(xiàng)式時(shí)間不確定性算法，其時(shí)間復(fù)雜性由一個(gè)多項(xiàng)式q(n)來(lái)界定。不失一般性，設(shè)q可在多項(xiàng)式時(shí)間內(nèi)被估值。因此，對(duì)于長(zhǎng)度為 n 的每個(gè)被接受的輸入，必然存在字符集上長(zhǎng)度至多為q(n)的某個(gè)猜想字符串，使算法A的檢驗(yàn)階段在不多于q(n)步內(nèi)回答“是

14、”。若| |=k，則所需要考慮的可能猜測(cè)的數(shù)目最多為kq(n)。對(duì)于一個(gè)長(zhǎng)度為 n 的給定輸入，通過(guò)應(yīng)用算法A的確定性檢驗(yàn)階段到相應(yīng)的kq(n)多個(gè)可能猜測(cè)字符串中的每一個(gè)，直到停止或運(yùn)行q(n)步，我們可以肯定地發(fā)現(xiàn)A對(duì)于該輸入是否有一個(gè)可接受計(jì)算。如果A在該時(shí)間界內(nèi)遇到一個(gè)導(dǎo)致可接受計(jì)算的猜測(cè)串，則該模擬過(guò)程回答“是”；否則回答“非”。這顯然形成了一個(gè)求解的確定性算法，而且該算法的時(shí)間復(fù)雜度將以q(n)kq(n) 為上界。其等價(jià)于O(2p(n) 。 NP完全問(wèn)題(1) 在非確定性圖靈機(jī)上時(shí)間復(fù)雜性為q(n)的判定問(wèn)題與在確定性圖靈機(jī)上時(shí)間復(fù)雜性為 q(n)kq(n) 的問(wèn)題相當(dāng)。 P NP

15、 ，問(wèn)：P = NP ？ 研究NP類中問(wèn)題之間的關(guān)系，從NP中找出一些具有特定性質(zhì)的、與P中問(wèn)題有顯著不同的問(wèn)題。形成了NP完全理論 多項(xiàng)式變換多項(xiàng)式變換：語(yǔ)言L11*到另一個(gè)語(yǔ)言L22*的多項(xiàng)式變換是指映射f: 1* 2*，滿足下面兩個(gè)條件： 1. 存在計(jì)算 f 的一個(gè)多項(xiàng)式時(shí)間DTM程序； 2. 對(duì)于所有的x1*有：xL1當(dāng)且僅當(dāng)f(x) L2。 記號(hào)： L1 L2 。 1 2 如果 L(1 , e1) L(2 , e2) NP完全問(wèn)題：稱一個(gè)語(yǔ)言L(判定問(wèn)題)是NP完全的，如果LNP( NP )，而且，對(duì)于任意LNP( NP )都有 L L ( ) NP完全問(wèn)題(2) 幾個(gè)性質(zhì)： 1.

16、若L L, LP，則L P; 2. 若L L，L L, 則 L L 3. 若判定問(wèn)題是NP完全的，P NP，則NPP； 4. 若L , L NP， L L 則 L NPC LNPC。 幾個(gè)典型的NP完全問(wèn)題 1. 可滿足性問(wèn)題 例：給定布爾變量之集以及上子句的一個(gè)集合C。 問(wèn)：是否存在的一個(gè)真值分配，使得C是可滿足的。 2. 圖的頂點(diǎn)覆蓋問(wèn)題 例：給定一個(gè)圖G(V,E)和一個(gè)正整數(shù)K|V| 。 問(wèn)：是否存在G的一個(gè)頂點(diǎn)數(shù)不超過(guò)K的覆蓋？NP完全問(wèn)題(3) 3. Hamilton回路問(wèn)題 例：給定一個(gè)圖G(V,E)。 問(wèn)：G含有一個(gè)Hamilton回路嗎？ 4. 劃分問(wèn)題 例：已知一個(gè)有限集合A

17、，其每個(gè)元素a都賦予一個(gè)權(quán)值s(a)Z+ 問(wèn)：是否存在A的子集A使得aA s(a) = aAA s(a)。 5.三元可滿足性問(wèn)題 3SAT 例：給定布爾變量的一個(gè)有限集合U及定義于其上的子句集C=c1,c2,cm, 其中|ci|=3, i=1,2,m。 問(wèn)：是否存在U之上的一個(gè)真值分配，使得C中所有的子句均被滿足？ 6. 三元精確覆蓋問(wèn)題 例：給定有限集X，|X|=3q，以及X的三元子集族C。 問(wèn)：C含X的一個(gè)精確覆蓋嗎？即存在C C，使得 cC c=X，而且X中的每個(gè)元素恰屬于C的一個(gè)子集。P=np證明新問(wèn)題是NPC問(wèn)題的方法(1) 證明 ；選取一個(gè)已知的NP完全問(wèn)題 ；構(gòu)造一個(gè)從 到 的變

18、換 ；證明 為一個(gè)多項(xiàng)式變換。Cook定理： 可滿足性問(wèn)題是NPC問(wèn)題。例例1 1 證明三元可滿足性問(wèn)題是NPC問(wèn)題。 選擇滿足性問(wèn)題作為參照物。設(shè)布爾變量集 及子句集 構(gòu)成SAT的一個(gè)一般性例子。我們構(gòu)造新的布爾變量集 及定義其上的三元子句集 ，使得 可滿足當(dāng)且僅當(dāng) 可滿足。 對(duì)于每個(gè)子句 ，設(shè) ，其中， 表示 中變量的非的全體。分三種情況討論： 1) 情形，此時(shí)令NPff12 ,nUu uu12 ,mCc ccUCCCjc12jkczzzizUUUU1k 證明新問(wèn)題是NPC問(wèn)題的方法(2) 情形2： ，令 情形3: ，令 ；情形4： ，令 ； 最后，令 ，往證： 可滿足當(dāng)且僅當(dāng) 可滿足設(shè)

19、是使 滿足的一個(gè)真賦值。以下說(shuō)明 可擴(kuò)充成滿足 的一個(gè)真賦值： 。 因?yàn)?中的變量可分解成不同的集合 ，而每個(gè) 的變量?jī)H出現(xiàn)在屬于 的子句中，我們僅需要說(shuō)明如何將 擴(kuò)充到各個(gè) 即可，且證明在上述四種情形的每一種情形下， 中的所有子句均被滿足。12121212121111,jjjjjjjjjjjjUyyCzyyzyyzyyzyy2k 1111212,jjjjjUyCzzyzzy3k jjjcCU,3k |13ijjUyik 1131221|14iikjjjijjkkCzzyyzyikyzz miimiiCCUUU11, CC,:FTUtCtC,: FTUtUUmjUj1, jUjCtjUjC證明

20、新問(wèn)題是NPC問(wèn)題的方法(3)若 屬于情形 或情形 ，則 中的子句已被 所滿足，從而可任意地?cái)U(kuò)展它到 ，例如，對(duì)所有的 ，令 若 是由情形 所確定的，那么 為空集，而 的賦值已經(jīng)使 中的單個(gè)子句取真值。 若 是由情形 所確定的，因?yàn)?為 的一種可滿足性真賦值，必然存在一個(gè)最小的整數(shù) ，使得變量 在 之下被賦予真值，且 。若 為1或2，則可對(duì) 令 ；若 為 或 ，則對(duì)于 ，令 ；其余情況，令 ， 。 容易證明，這些選擇將保證 中所有的子句均被滿足，進(jìn)而 中的所有子句也均被賦值 所滿足。反之，若 為 的一個(gè)可滿足性真賦值，則不難證明 對(duì)于 中變量的限制必形成對(duì) 的一個(gè)可滿足性真賦值。jU1k2kj

21、CtjUjUyTyt)( jU3kjUtjjcC jU3ktCllzt0l l31:kiiFytij)( l1kk31:kiiTytij)( ()12ijt yTil ，31)( kilFytij，jCC t tC tUC證明新問(wèn)題是NPC問(wèn)題的方法(4)至此，我們證明了 可滿足當(dāng)且僅當(dāng) 可滿足。 要證明上述變換可在多項(xiàng)式時(shí)間內(nèi)完成，只需注意到 中三元子句的數(shù)目被 的一個(gè)多項(xiàng)式所界定。也就是說(shuō)，3SAT例子的大小由SAT例子的大小的一個(gè)多項(xiàng)式函數(shù)所界定。由此，根據(jù)上述構(gòu)造方法，不難證明它是一個(gè)多項(xiàng)式變換。 例例2 證明圖的頂點(diǎn)覆蓋問(wèn)題VC是NPC-問(wèn)題 首先，圖的頂點(diǎn)覆蓋問(wèn)題是NP問(wèn)題。因?yàn)榍?/p>

22、解它的不確定性算法只需猜測(cè)頂點(diǎn)的一個(gè)子集，然后在多項(xiàng)式時(shí)間內(nèi)就可以檢驗(yàn)該子集是否包含每條邊的至少一個(gè)端點(diǎn)，并具有適當(dāng)?shù)拇笮?，即該頂點(diǎn)子集中頂點(diǎn)的個(gè)數(shù)不超過(guò)限定的值。 選三元可滿足性問(wèn)題做參照物。設(shè) 為3SAT的一個(gè)一般性例子。我們要構(gòu)造一個(gè)圖 和一個(gè)正整數(shù) ，使得 有一個(gè)頂點(diǎn)數(shù)不超過(guò) 的覆蓋，當(dāng)且僅當(dāng)CCCnm1212:,nmUuuuCccc),(EVG |VK GK證明新問(wèn)題是NPC問(wèn)題的方法(5) 是可滿足的。 對(duì)每個(gè)變量 ,定義 ，其中 ；對(duì)于每個(gè)子句 ，設(shè) ，構(gòu)造一個(gè)三角形 ，其中并且構(gòu)造新的邊集 ，如下圖。 CUui),(iiiEVT ,( ,)iiiiiiVu uEu uCcjjj

23、jjcxyz),(jjjEVS 123121323( ),( ),( ) ,( ),( ) ,( ),( ) ,( ),( )jjVA jAjAjEA jAjA jAjAjAj 123( ),( ),( ),jjjjEA jxAjyAjzSju1u2u3u4unv1v2v3v4vnA1(j)A2(j)A3(j)A3(k)A2(k)A1(k)xjyjzjxkykzk證明新問(wèn)題是NPC問(wèn)題的方法(6) 其中 。令 ，由于 ，以及 均為有 限值，上述構(gòu)造圖的過(guò)程一定在多項(xiàng)式時(shí)間內(nèi)完成。以下證明： 是可滿足的當(dāng)且僅當(dāng)G有一個(gè)頂點(diǎn)數(shù)不超過(guò) 的覆蓋。 設(shè) 是G的一個(gè)頂點(diǎn)覆蓋， 。由圖G的構(gòu)造， 必然包含每

24、 個(gè) 中至少一個(gè)頂點(diǎn)，和每個(gè) 中至少兩個(gè)頂點(diǎn)，這已經(jīng)給出了至 少 個(gè)頂點(diǎn)，故 必然含有每個(gè) 中恰好一個(gè)頂點(diǎn)和每個(gè) 中恰好兩個(gè)頂點(diǎn)。據(jù)此給出U的一種真賦值 如下： 當(dāng) 時(shí)， ；而 時(shí)， 。 為了說(shuō)明該賦值滿足每個(gè)子句 ，考慮 中的三條邊。這些邊 中恰有兩條可被 中的頂點(diǎn)覆蓋，剩下的一條邊必由屬于 的 某個(gè) 中的一個(gè)頂點(diǎn)覆蓋。但這意味著子句 中的相應(yīng)變量，或niuvii, 2 , 1,11111,nmnmmijijjijijjVVVEEEEEVG,mnK2| 23 ,|336VnmEnmmnmKCKVV KV | |ViTjSmnK2ViTjS,:FTUtVuiTuti)(VuiFuti)(Ccj

25、jEVVjViVjc證明新問(wèn)題是NPC問(wèn)題的方法(7)者是 或者是 ，在賦值 之下取值為真，從而 可由 滿足。反之，如果 為C的一個(gè)可滿足性真賦值，我們構(gòu)造G的一個(gè)覆蓋如下：對(duì)于 中的頂點(diǎn)，如果 ，選取 ，如果 則選取 ；對(duì)于 中的頂點(diǎn)，由于 中至少有一個(gè)取真值 ，不妨設(shè) ，則在前面諸 中頂點(diǎn)的選取中， 必然被選取，此時(shí)我們?cè)?中只需選取頂點(diǎn) 、 即可。 上述方法選出的頂點(diǎn)集顯然是G的覆蓋，而且頂點(diǎn)數(shù)恰好為 。 例例3 證明：Steiner樹(shù)問(wèn)題是NPC-問(wèn)題 例：給定圖 ，對(duì)其每條邊 都有相應(yīng)的權(quán) ，另外有G的頂點(diǎn)子集 ，某個(gè)界 。 問(wèn)：是否存在G的一棵子樹(shù) ，使 ，而且 ？ iuiuttj

26、c,:FTUtiVTuti)(iuFuti)(iu)1 (mjVjjjjjcxyzTTxtj)(iVjxjV2( )Aj3( )AjmnK2),(EVG EeZew )(VR ZB),(11EVT EEVVR11,BewEe1)(證明新問(wèn)題是NPC問(wèn)題的方法(8) 為證明Steiner樹(shù)問(wèn)題是NPC的,選X3C問(wèn)題作為參照物： 三元子集族 ，構(gòu)造Steiner樹(shù)問(wèn)題的相應(yīng)例子如下： 取 ，其中 ； 令所有邊的權(quán)值為1， ， 。顯然這一構(gòu)造過(guò)程可在多項(xiàng) 式時(shí)間內(nèi)完成。 qxxxX321,ncccC,21),(EVG 00,|1,|,1,13iijjiVvCX Ev cinc xxcinjq Xv

27、R0qB4。CiqCi2Ci1v0 x1x2x3x3qC/X證明新問(wèn)題是NPC問(wèn)題的方法(9)如果 為 的一個(gè)精確覆蓋，則取 ，其中 ，由于每個(gè) 恰好出現(xiàn)在 的某個(gè)三元子集里，故 是連通的無(wú)圈圖，因而是一棵樹(shù)。而且 。注意到 ，且 ，由此知Steiner樹(shù)問(wèn)題的回答為“是”。 反之，若 為 的一棵Steiner樹(shù)， ，則每個(gè) 都是 的頂點(diǎn)。不妨設(shè)每個(gè) 都是 的葉頂點(diǎn)，因?yàn)椋駝t的話，頂點(diǎn) 的度數(shù)大于1，及存在邊 刪去其中一條邊，如 。由于 ， 不可能都屬于 ，否則 包含有圈，將不屬于 的那條邊添入 得到另一棵樹(shù) ，它是總權(quán)值未變的Steiner樹(shù)。但這棵樹(shù)包含X中的頂點(diǎn)作為葉頂點(diǎn)的個(gè)數(shù)比 的多

28、，這樣做下去，必然找到一棵Steiner樹(shù)，在其上，所有X中的頂點(diǎn)都是葉頂點(diǎn)。再由連通性，每個(gè) 恰好和某一個(gè) 在 中鄰接，令 ，則 顯然是 的一個(gè)精確覆蓋CC X),(11EVT XCccvVii|0110,|,|,13iiijijiEv ccCc xcC xcjqjxCTqE4|11VR BEewEe|)(11) , (EVT ),(EVG VR qjxj31TjxTjx 12,jijix cx cEE1,jix c10,iv c20,iv cETEE1TTjxicT|,13iijCcc xTjqCX證明新問(wèn)題是NPC問(wèn)題的方法(10) 例例4 證明 0/1背包判定問(wèn)題是NPC問(wèn)題 例：給定

29、一個(gè)有限集合 ，對(duì)每一個(gè) ，對(duì)應(yīng)一個(gè)值 和相應(yīng)的值 。另外，還有一個(gè)容量約束 和一個(gè)價(jià)值目標(biāo) 。 問(wèn)：是否存在 的一個(gè)子集 , 使得 ，而且 顯然，0/1背包問(wèn)題是NP問(wèn)題。 現(xiàn)在，我們考慮特殊的 0/1 背包問(wèn)題：對(duì)所有的 有 , 且取 。 顯然，這個(gè)0/1背包判定問(wèn)題回答為“是”當(dāng)且僅當(dāng)集合 的劃分問(wèn)題回答為“是”?？梢?jiàn)，劃分問(wèn)題恰是0/1 背包問(wèn)題的特例。從而由劃分問(wèn)題是NPC問(wèn)題推得0/1背包判定問(wèn)題是NPC問(wèn)題。 XxX( )w xZ( )p xZMZZKXXX( )x Xw uM( )x Xp xKxX( )( )w xp x1( )2x XMKw xXNP難問(wèn)題(1) 圖靈歸約圖

30、靈歸約：設(shè) 和 是兩個(gè)問(wèn)題，稱 可圖靈歸約為 ，記作 ，如果存在求解 的一個(gè)算法 ，它多次調(diào)用求解 的算法 作為其子程序。 庫(kù)克歸約庫(kù)克歸約：假設(shè) ，且求解 的程序 每次調(diào)用求解 的子程序 均需用單位時(shí)間，若 為一個(gè)多項(xiàng)式時(shí)間確定算法。稱 為從 到 的多項(xiàng)式歸約。（也稱庫(kù)克歸約）。 庫(kù)克歸約的定義不限于判定問(wèn)題，也可適用于函數(shù)類問(wèn)題（如最優(yōu)化）。如果問(wèn)題 可以歸約到 ，則 至少和 一樣難。 NP難問(wèn)題：難問(wèn)題：對(duì)于問(wèn)題 ，如果存在一個(gè)NP完全問(wèn)題 ，使得 可多項(xiàng)式時(shí)間圖靈歸約到 ，則稱 是NP困難的。 NP難問(wèn)題不要求是NP類問(wèn)題。 第 重子集問(wèn)題 例：已知整數(shù) ； 問(wèn)：存在 個(gè)不同的子集 ，

31、使得對(duì)于 有 ？121212T 11A22A2A1A1A121221kLkcccn,21k12,1,2, kS SSnki, 1 LciSjj12T 1A21NP難問(wèn)題(2) 利用劃分問(wèn)題(NP完全問(wèn)題)證明第k最重子集問(wèn)題是NP難問(wèn)題 事實(shí)上，設(shè) 是劃分問(wèn)題的一般例子，假設(shè)我們已經(jīng) 有個(gè)算法 可以用來(lái)解第 最重子集問(wèn)題，則可設(shè)計(jì)出求解 劃分問(wèn)題的算法如下： 首先，若 為奇數(shù)，則立即推出回答問(wèn)題否?，F(xiàn)在，假定 是偶數(shù)，并令 ，用算法 作為子程序，按下列二分 搜索技術(shù)確定重至少是 的不同子集的數(shù)目 ： 1) 令 ； 2) 若 ，置 ，且停機(jī)； 3) 令 ，并調(diào)用算法 。 4) 若回答為“是”，則

32、令 ，轉(zhuǎn)2)；否則，令 ，轉(zhuǎn)2) 以上過(guò)程通過(guò)恰好 次調(diào)用 ,即可找到 。至此，只需再調(diào) 用一次該算法即可給出所考慮劃分問(wèn)題例子的答案，即調(diào)用 。若該調(diào)用的答案為“是”，則S中所有重至少為L(zhǎng)的子 集也必滿足其重至少為L(zhǎng)+1，因此，S沒(méi)有重為L(zhǎng)的子集，故對(duì)劃分 問(wèn)題的回答為“否”。相反，若該調(diào)用的回答為“否”，則意味著 存在,21ncccS,LkSAkniic1niic1niicL121,LkSAL*KnKK2, 0maxmin1minmax KKmin*KK 2/ )(maxminKKK,LKSAKKminKKmaxn,LKSA*K 1*,LKSANP難問(wèn)題(3)某一個(gè)S的子集，使得其重為L(zhǎng)，

33、對(duì)劃分問(wèn)題的回答為“是”。 由上述迭代過(guò)程容易看出，若假設(shè)每次調(diào)用算法A只需要單位時(shí)間，則以上即給出了求解劃分問(wèn)題的一個(gè)多項(xiàng)式時(shí)間算法。也就是說(shuō)，我們證明了劃分問(wèn)題可多項(xiàng)式時(shí)間歸約到第k個(gè)最重子集問(wèn)題。 旅行商問(wèn)題是NP難問(wèn)題 旅行商問(wèn)題不是NP的。因?yàn)閷?duì)其解的任一猜想，要檢驗(yàn)它是否是最優(yōu)的，需要同所有其它的環(huán)游比較，這樣的環(huán)游會(huì)有指數(shù)多個(gè)，因而不可能在多項(xiàng)式時(shí)間內(nèi)完成。 用圖的Hamilton回路問(wèn)題(NPC問(wèn)題)證明旅行商問(wèn)題是NP難的 已知無(wú)向圖G=(V,E),|V|=n,構(gòu)造其對(duì)應(yīng)的旅行商問(wèn)題如下：這一變換可以在多項(xiàng)式時(shí)間內(nèi)完成，而且，圖G有Hamilton回路的充要條件是上述構(gòu)建的旅行商問(wèn)題有解，且其解對(duì)應(yīng)的路程長(zhǎng)度為n。故我們證明了對(duì)稱旅行商問(wèn)題是NP