計算理論_計算復(fù)雜性_2016

1、教材教材: 1王王 王曉東王曉東,計算機算法設(shè)計與分析計算機算法設(shè)計與分析(第第4版版),電子工業(yè)電子工業(yè). 2S 唐常杰等譯唐常杰等譯, Sipser著著, 計算理論導(dǎo)引計算理論導(dǎo)引, 機械工業(yè)機械工業(yè). 參考資料參考資料:3C 潘金貴等譯潘金貴等譯, Cormen等著等著, 算法導(dǎo)論算法導(dǎo)論, 機械工業(yè)機械工業(yè). 4M 黃林鵬等譯黃林鵬等譯, Manber著著, 算法引論算法引論-一種創(chuàng)造性方法一種創(chuàng)造性方法, 電子電子. 5劉劉 劉汝佳等劉汝佳等, 算法藝術(shù)與信息學(xué)競賽算法藝術(shù)與信息學(xué)競賽, 清華大學(xué)清華大學(xué).6L Lewis等著等著, 計算理論基礎(chǔ)計算理論基礎(chǔ), 清華大學(xué)清華大學(xué). 計

2、算理論與計算理論與算法分析設(shè)計算法分析設(shè)計 劉劉 慶慶 暉暉 計算理論計算理論 第三部分第三部分 計算復(fù)雜性計算復(fù)雜性 第第7章章 時間復(fù)雜性時間復(fù)雜性1. 時間復(fù)雜性時間復(fù)雜性 0k1k | k 0 的時間復(fù)雜性分析的時間復(fù)雜性分析 2. 不同模型的運行時間比較不同模型的運行時間比較 單帶與多帶單帶與多帶 確定與非確定確定與非確定 3. P類與類與NP類類4. NP完全性及完全性及NP完全問題完全問題一一. 時間復(fù)雜度時間復(fù)雜度 時間復(fù)雜度定義時間復(fù)雜度定義 0k1k | k 0 的時間復(fù)雜度分析的時間復(fù)雜度分析 時間復(fù)雜性時間復(fù)雜性 判定器判定器M的的運行時間運行時間或或時間復(fù)雜度時間復(fù)雜

3、度是是f:NN, f(n)是是M在在所有長為所有長為n的輸入的輸入上運行的最大步數(shù)上運行的最大步數(shù). 若若f(n)是是M的運行時間的運行時間, 則稱則稱 M在時間在時間f(n)內(nèi)運行內(nèi)運行 或或 M是是f(n)時間圖靈機時間圖靈機舉例舉例:大大O與小與小o記法記法對于函數(shù)對于函數(shù)f,g:NR+,記記f(n)=O(g(n),若存在若存在c0使得使得 cngnfn)()(lim記記f(n)=o(g(n),若若 0)()(limngnfn分析算法分析算法討論語言討論語言A = 0k1k | k 0 的復(fù)雜性的復(fù)雜性:M1=“對輸入串對輸入串w: 1)掃描帶掃描帶,如果在如果在1的右邊發(fā)現(xiàn)的右邊發(fā)現(xiàn)0

4、,則拒絕則拒絕. 2)如果如果0和和1都在帶上都在帶上,就重復(fù)下一步就重復(fù)下一步. 3) 掃描帶掃描帶,刪除一個刪除一個0和一個和一個1. 4)如果帶上同時沒有如果帶上同時沒有0和和1,就接受就接受.”時間分析時間分析: (1) 2n=O(n), 4) n=O(n), (2) 2n=O(n) + (3) 2n=O(n) (n/2) = O(n2)所以所以M1的運行時間是的運行時間是O(n2).時間復(fù)雜性類時間復(fù)雜性類定義定義: 對于函數(shù)對于函數(shù)t:NN, 時間復(fù)雜性類時間復(fù)雜性類 TIME( t(n) ) 定義為定義為:TIME(t(n) = L | 存在存在O(t(n)時間時間TM判定判定L

5、 因為因為M1是時間是時間O(n2)圖靈機圖靈機,所以所以A=0k1k:k 0 TIME(n2).是否存在更快的是否存在更快的TM判定判定A呢呢?圖靈機圖靈機M2M2=“對輸入串對輸入串w: 1)掃描帶掃描帶,若若1的右邊有的右邊有0,則拒絕則拒絕. 2)若若0,1都在帶上都在帶上,重復(fù)以下步驟重復(fù)以下步驟. 3) 檢查帶上檢查帶上0,1總數(shù)的奇偶性總數(shù)的奇偶性, 若是奇數(shù)若是奇數(shù),就拒絕就拒絕. 4) 再次掃描帶再次掃描帶, 第第1個個0開始開始,隔隔1個個0刪除刪除1個個0; 第第1個個1開始開始,隔隔1個個1刪除刪除1個個1. 5)若帶上若帶上同時沒有同時沒有0和和1,則接受則接受. 否

6、則拒絕否則拒絕.” O(n)O(n)O(n)O(n)O(n) log n總時間總時間:O(nlogn)0k1k|k 0 TIME(nlogn)由圖靈機由圖靈機M2知道知道A TIME(n log n)有沒有有沒有更快的圖靈機識別更快的圖靈機識別A?對于對于單帶單帶確定圖靈機確定圖靈機, 由由定理定理: 時間時間o(nlogn)的單帶圖靈機判定的語言的單帶圖靈機判定的語言 是正則語言是正則語言. TIME(o(nlogn) 正則語言類正則語言類 TIME(n) 正則語言類正則語言類 = TIME(n) = TIME(o(nlogn)非正則語言非正則語言 0k1k | k 0 TIME(o(nlo

7、gn) 二二. 不同模型的時間復(fù)雜度比較不同模型的時間復(fù)雜度比較 單帶與多帶單帶與多帶 確定與非確定確定與非確定 單帶與多帶運行時間比較單帶與多帶運行時間比較 0k1k | k 0 有有O(n)時間雙帶圖靈機時間雙帶圖靈機 M3=“對輸入串對輸入串w: 1) 掃描掃描1帶帶,如果在如果在1的右邊發(fā)現(xiàn)的右邊發(fā)現(xiàn)0,則拒絕則拒絕. 2) 將將1帶的帶的1復(fù)制到復(fù)制到2帶上帶上. 3) 每刪除一個每刪除一個1帶的帶的0就刪除一個就刪除一個2帶的帶的1. 4) 如果兩帶如果兩帶上同時沒有上同時沒有0和和1,就接受就接受.” 定理定理:設(shè)函數(shù)設(shè)函數(shù)t(n) n, 則每個則每個t(n)時間多帶時間多帶TM

8、 和某個和某個O(t2(n)時間單帶時間單帶TM等價等價. 0k1k|k 0的的O(n)時間雙帶圖靈機時間雙帶圖靈機q0q1qaq2RR$00RR0LR1LR1LR$NTM的運行時間的運行時間定義定義: 對非確定型判定器對非確定型判定器N, 其運行時間其運行時間f(n)是是 在在所有所有長為長為n的輸入上的輸入上, 所有所有分支的最大步數(shù)分支的最大步數(shù).f(n)接受接受/拒絕拒絕.f(n).TMNTM定理定理: 設(shè)設(shè)t(n) n, 則每個則每個 時間時間t(n)NTM都有一等價的都有一等價的 時間時間2O(t(n)TM. NTIME(t(n) TIME (2O(t(n) 三三. P與與NP 多

9、項式時間多項式時間運行時間相差多項式可以認(rèn)為是小的運行時間相差多項式可以認(rèn)為是小的 相差指數(shù)可以認(rèn)為是大的相差指數(shù)可以認(rèn)為是大的.例如例如:n3與與2n,對于對于n=1000.有關(guān)有關(guān)素性測試素性測試: Prime= p | p是素數(shù)是素數(shù) 如何編碼如何編碼? 一進(jìn)制一進(jìn)制,二進(jìn)制二進(jìn)制,十進(jìn)制十進(jìn)制?典型的指數(shù)時間算法來源于典型的指數(shù)時間算法來源于蠻力搜索蠻力搜索.有時通過深入理解問題可以避免蠻搜有時通過深入理解問題可以避免蠻搜.2001年年P(guān)rime被證明存在被證明存在多項式時間算法多項式時間算法. P類類定義定義:P是是單帶確定單帶確定TM在在 多項式時間內(nèi)可判定的問題多項式時間內(nèi)可判定

10、的問題,即即 P = k TIME(nk)P類的重要性在于類的重要性在于:1) 對于所有與單帶確定對于所有與單帶確定TM等價的等價的模型模型,P不變不變.2) P大致對應(yīng)于在計算機上大致對應(yīng)于在計算機上實際可解實際可解的問題的問題. 研究的核心是一個問題是否屬于研究的核心是一個問題是否屬于P類類.NP類類NTIME(t(n)=L|L可被可被O(t(n)時間時間NTM判定判定.定義定義:NP是是單帶非確定單帶非確定TM在在 多項式時間內(nèi)可判定的問題多項式時間內(nèi)可判定的問題,即即 NP = k NTIME(nk) EXP = k TIME(2(nk) P NP EXP P EXP 一些一些P問題問

11、題有些問題初看起來不屬于有些問題初看起來不屬于P求最大公因子求最大公因子: 歐幾里德算法歐幾里德算法, 輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法模模p指數(shù)運算指數(shù)運算ab mod p素性測試素性測試 等等等等以增加空間復(fù)雜性來減小時間復(fù)雜性以增加空間復(fù)雜性來減小時間復(fù)雜性 上下文無關(guān)上下文無關(guān)語言語言 有有O(n3)判定器判定器 快速驗證快速驗證HP = |G是包含從是包含從s到到t的的 哈密頓路徑哈密頓路徑的有向圖的有向圖CLIQUE=|G是有是有k團(tuán)的無向圖團(tuán)的無向圖目前目前沒有快速算法沒有快速算法,但其但其成員成員是可以快速驗證的是可以快速驗證的. 注意注意:HP的的補補可能可能不是可以快速驗證的不是可以快

12、速驗證的.快速驗證的特點快速驗證的特點:1. 只需要對語言中的串能快速驗證只需要對語言中的串能快速驗證.2. 驗證需要借助額外的信息驗證需要借助額外的信息:證書證書,身份證身份證.NP問題問題團(tuán)團(tuán):無向圖的完全子圖無向圖的完全子圖(所有節(jié)點都有邊相連所有節(jié)點都有邊相連).CLIQUE=|G是有是有k團(tuán)的無向圖團(tuán)的無向圖定理定理: CLIQUE NP.N=“對于對于輸入輸入,這里這里G是一個圖是一個圖: 1)非確定地選擇非確定地選擇G中中k個節(jié)點的子集個節(jié)點的子集c. 2)檢查檢查G是否包含連接是否包含連接c中節(jié)點的所有邊中節(jié)點的所有邊. 3)若是若是,則接受則接受;否則否則,拒絕拒絕.”哈密頓

13、路徑問題哈密頓路徑問題HP NPHP=|G是包含從是包含從s到到t的的 哈密頓路徑哈密頓路徑的有向圖的有向圖P時間內(nèi)判定時間內(nèi)判定HP的的NTM:N1=“對于輸入對于輸入: 1)非確定地選非確定地選G的所有節(jié)點的排列的所有節(jié)點的排列p1,pm. 2)若若s=p1,t=pm,且對每個且對每個i, (pi,pi+1)是是G的邊的邊, 則接受則接受;否則拒絕否則拒絕.”P與與NP P=成員資格可以成員資格可以快速快速判定判定的語言類的語言類.NP=成員資格可以成員資格可以快速快速驗證驗證的語言類的語言類.顯然有顯然有 P NP但是否有但是否有 P=NP ?看起來難以想象看起來難以想象, 但是現(xiàn)在沒有

14、發(fā)現(xiàn)反例但是現(xiàn)在沒有發(fā)現(xiàn)反例.PNPP=NP當(dāng)代數(shù)學(xué)與當(dāng)代數(shù)學(xué)與理論計算機理論計算機共同的難題共同的難題. NP完全性的定義完全性的定義 SAT是是NP完全問題完全問題 一些一些NP完全問題完全問題NP完全性完全性Cook和和Levin于于70s證明證明NP中中某些問題某些問題的復(fù)雜性與的復(fù)雜性與 整個整個NP類類的復(fù)雜性相關(guān)聯(lián)的復(fù)雜性相關(guān)聯(lián), 即即:若這些問題中的任一個找到若這些問題中的任一個找到P時間算法時間算法,則則P=NP.這些問題稱為這些問題稱為NP完全問題完全問題.理論意義理論意義:兩方面兩方面1)研究研究P與與NP關(guān)系可以只關(guān)注于一個問題的算法關(guān)系可以只關(guān)注于一個問題的算法.2)

15、可由此說明一個可由此說明一個問題目前還沒有問題目前還沒有快速算法快速算法.合取范式合取范式 布爾變量布爾變量: 取值為取值為1和和0( T, F )的變量的變量. 布爾運算布爾運算: AND( ),OR ( ),NOT ( ). 布爾公式布爾公式. 例例: 1 = ( ( x) y ) ( x ( z) ), 2 = ( x) x 稱稱 可滿足可滿足, 若存在布爾變量的若存在布爾變量的0,1賦值使得賦值使得 =1. 不可滿足不可滿足 永真永真 合取范式合取范式: 正負(fù)文字正負(fù)文字(變量變量,變量的非變量的非) 子句子句(文字的或文字的或) ( x1) x2 ( x3) (x2 ( x3) x4

16、 x5) ( x4) x5) 合取范式合取范式cnf (conjunctive normal form) 3cnf: 每個子句文字?jǐn)?shù)不大于每個子句文字?jǐn)?shù)不大于3, 2cnf: 每個子句文字?jǐn)?shù)不每個子句文字?jǐn)?shù)不大于大于2 可滿足問題可滿足問題SAT 可滿足性問題可滿足性問題: SAT = | 是可滿足是可滿足的布爾公式的布爾公式 二元可滿足性問題二元可滿足性問題: 2SAT = | 是可滿足的是可滿足的2cnf 三元可滿足性問題三元可滿足性問題: 3SAT = | 是可滿足的是可滿足的3cnf 二元可滿足問題二元可滿足問題2SAT P1. 當(dāng)當(dāng)2cnf中有子句是單文字中有子句是單文字x, 則反復(fù)

17、執(zhí)行則反復(fù)執(zhí)行清洗清洗 1.1 由由x賦值賦值, 1.2 刪去含刪去含x的子句的子句, 1.3 刪去含刪去含 x的文字的文字 若清洗過程出現(xiàn)相反單文子子句若清洗過程出現(xiàn)相反單文子子句, 則清洗則清洗失敗并結(jié)束失敗并結(jié)束 (x1 x2) (x3x2) (x1) ( x1 x2) (x3 x4) ( x3 x5) ( x4x5) ( x3 x4)(x3x2) ( x2) (x3 x4) ( x3 x5) ( x4x5) ( x3 x4)(x3 x4) ( x3 x5) ( x4x5) ( x3 x4)2. 若無單文字子句若無單文字子句, 則任選變量賦真則任選變量賦真/假值各清洗一次假值各清洗一次

18、若兩次都清洗失敗若兩次都清洗失敗, 則回答不可滿足則回答不可滿足. x3: (x5) ( x4x5) (x4) ( x4) (x4) 失敗失敗 x3: (x4) ( x4x5) ( x5) 成功成功3. 若成功清洗后有子句剩下若成功清洗后有子句剩下, 則則繼續(xù)繼續(xù)2. 否則否則, 回答可滿足回答可滿足.注注: 見見S習(xí)題習(xí)題7.23, 作者給出的答案與清洗算法作者給出的答案與清洗算法等價等價多項式時間映射歸約與多項式時間映射歸約與C-L定理定理 Cook-Levin定理定理: SAT P P=NP. 定義定義:多項式時間多項式時間可計算函數(shù)可計算函數(shù)f: *. 定義定義:稱稱A可可多項式時間多

19、項式時間映射歸約映射歸約到到B (A PB), 若存在若存在多項式時間多項式時間可計算函數(shù)可計算函數(shù)f: *, w*, w A f(w) B. 函數(shù)函數(shù)f稱為稱為A到到B的的多項式時間多項式時間歸約歸約. 通俗地說通俗地說: f 將將A的實例編碼轉(zhuǎn)換為的實例編碼轉(zhuǎn)換為B的實例編碼的實例編碼. Cook-Levin定理定理: 對任意對任意A NP都有都有A P SAT. 定理定理1: 若若 A P B, 且且 B P, 則則 A P. 注注: 定理定理1說明說明, 若若SAT P, 則則 NP = P .多項式時間映射歸約的作用多項式時間映射歸約的作用 輸入輸入w f f(w) M y/n w*

20、, w A f(w) B. 定理定理1: 若若 A P B, 且且 B P, 則則 A P. 證明證明: 設(shè)設(shè) f: *是是A到到B的的P時間歸約時間歸約, B有有P時間判定器時間判定器M, 則則 N=“輸入輸入w, 計算計算M(f(w), 輸出輸出M的運行結(jié)果的運行結(jié)果” 在多項式時間內(nèi)判定在多項式時間內(nèi)判定A. 利用利用f和和B的判定的判定器器 構(gòu)造構(gòu)造A的判定器的判定器 定理定理: 3SAT P CLIQUE3SAT = | 是可滿足的是可滿足的3cnf公式公式 CLIQUE = | G是有是有k團(tuán)的無向圖團(tuán)的無向圖 .證明證明:設(shè)設(shè) =(a1 b1 c1) (ak bk ck),有有k

21、個子句個子句. f( ) = , G有有k組節(jié)點組節(jié)點,每組每組3個個; 同組同組節(jié)點無邊相連節(jié)點無邊相連, 相反標(biāo)記相反標(biāo)記無邊相連無邊相連.f(x1 x1 x2) (x1 x2 x2) (x1 x2 x2) = x1 x1 x2 x1 x2 x2 x1 x2 x2 需證需證:3SAT (G,k) CLIQUE , 3SATf( ) CLIQUE () 3SAT 變量賦值變量賦值(x1=0, x2=1)使得使得 =1 k團(tuán)團(tuán)(每組挑一個真頂點得到每組挑一個真頂點得到k團(tuán)團(tuán), 非同組非相反非同組非相反) f( ) () CLIQUE.x1 x1 x2 x1 x2 x2 x1 x2 x2 NP完

22、全性完全性 定義定義:語言語言B稱為稱為NP完全的完全的(NPC),若它滿足若它滿足: 1) B NP; 2) A NP, 都有都有A PB. 定理定理1:若若 A P B, 且且 B P, 則則 A P. 定理定理2: 若若B是是NPC, 且且B P, 則則P=NP. 定理定理3: 若若B是是NPC, B PC,且且C NP, 則則C是是NPC. 證明證明: A NP, (A P B) + (B P C) A P C Cook-Levin定理定理: SAT是是NP完全問題完全問題. 推論推論: CLIQUE是是NPC. 輸入輸入w f f(w) M y/n w*, w A f(w) B.利用

23、利用f和和B的判定的判定器器 構(gòu)造構(gòu)造A的判定器的判定器 Cook-Levin定理的證明步驟定理的證明步驟 定義定義:語言語言B稱為稱為NP完全的完全的(NPC),若它滿足若它滿足: 1) B NP; 2) A NP, 都有都有A PB. Cook-Levin定理定理: SAT是是NP完全問題完全問題. 證明步驟證明步驟: 1. SAT NP(?), 2. A NP, A P SAT(?) N=“對于輸入對于輸入, 是一個布爾公式是一個布爾公式: 1)非確定地非確定地選擇選擇 所有變量的賦值所有變量的賦值T. 2)檢查在賦值檢查在賦值T下是否下是否 =1 3)若是若是,則接受則接受;否則否則,

24、拒絕拒絕.”SAT是是NP完全問題完全問題 要證明要證明: 1) SAT NP. 2) A NP, 都有都有 A P SAT. 思想思想: 將字符串對應(yīng)到布爾公式將字符串對應(yīng)到布爾公式 利用接受的形式定義利用接受的形式定義. 過程過程: 任取任取A NP, 設(shè)設(shè)N是是A的的nk時間時間NTM. w(|w|=n), N接受接受w N有長度小于有長度小于nk的接受格局序列的接受格局序列 能填好能填好N在在w上的上的畫面畫面(一個一個nk nk表格表格) f(w)可滿足可滿足 結(jié)論結(jié)論: SAT是是NP完全的完全的N接受接受w能填好能填好N在在w上的畫面上的畫面#q0w0w1wn#nk nk 起始格

25、局起始格局 第第2個格局個格局 第第nk個格局個格局 窗口窗口 能填好畫面能填好畫面: 第一行是起始格局第一行是起始格局 上一行能產(chǎn)生上一行能產(chǎn)生(或等于或等于)下一行下一行 畫面中有接受狀態(tài)畫面中有接受狀態(tài)構(gòu)造布爾公式構(gòu)造布爾公式f(w) 能能填好畫面填好畫面f(w)可滿足可滿足 f(w)=, = cellstartmoveaccept . 對于任意賦值對于任意賦值: 1. cell =1 每格有且只有每格有且只有一個符號一個符號; 2. start =1 第一行是起始格局第一行是起始格局; 3. accept =1 表格中有接受狀態(tài)表格中有接受狀態(tài); 4. move=1 每行由上一行格局每

26、行由上一行格局產(chǎn)生產(chǎn)生. w, w A SAT 即即 A m SAT 若若|是是|w|的多項式的多項式, 則有則有A P SAT構(gòu)造構(gòu)造 cell)(,1celltjisjitssjisnjixxxk 長長O(n2k) cell = 1 每格有且只有每格有且只有一個符號一個符號; 的變量的變量: xi,j,s, i,j=1,nk, s Q# xi,j,s : 第第i行第行第j列是否填了符號列是否填了符號s)()()()(3,2,3,1 ,2,1 ,3,2,1 ,jijijijijijijijijixxxxxxxxx 構(gòu)造構(gòu)造 start# ,# ,startknwqxxxx131211110

27、長長O(nk) start = 1 第一行是起始格局第一行是起始格局; 構(gòu)造構(gòu)造 acceptaccept,acceptqjinjixk 1 長長O(n2k) accept = 1 表格中有接受狀態(tài)表格中有接受狀態(tài) 構(gòu)造構(gòu)造 move = cellstartmove accept. move確定表的每行是上一行的合法結(jié)果確定表的每行是上一行的合法結(jié)果. 只需判斷每個只需判斷每個2 3窗口是否窗口是否“合法合法”.合法窗口合法窗口設(shè)設(shè) (q1,b)=(q2,c,L),(q2,e,R),a,d,s,t是任意符號是任意符號,則則aq1bq2acaq1baeq2daq1daeasbasbstastq2

28、bsacsaabtastaq1baaq1aq1bq1aq1合法合法 窗口窗口 非法非法 窗口窗口 61621, 1, 1, 1,1moveajiajiaaanjixxk 是合法窗口是合法窗口 長長O(n2k)A PSAT, SAT是是NPC61621, 1, 1, 1,1moveajiajiaaanjixxk 是合法窗口是合法窗口 )(,1celltjisjitssjisnjixxxk # ,# ,startknwqxxxx131211110 accept,acceptqjinjixk 1 f(w) = w A SAT, | = O(n2k) = cellstartmoveaccept . 推

29、論推論:3SAT是是NP完全的完全的只需將前面的只需將前面的 改造為改造為3cnf公式公式. = cellstartmove accept.# ,# ,startknwqxxxx131211110 accept,acceptqjinjixk 1 )(,1celltjisjitssjisnjixxxk 任取變量賦值任取變量賦值 a1 a2 ak = 1 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) 存在新變量存在新變量z的賦值使得的賦值使得 ( a1 a2 ak-2 z ) ( z ak-1 ak ) =1改造后公式長度最多是原來的改造后公式長度最多是原來的3倍倍 move的改造的改造分配律分配律 (a b) c = (a

30、 c) (b c) (a b) (c d) (e f) = (a c e) (a c f) 設(shè)合法窗口有設(shè)合法窗口有M個個, 則則 move原長度是原長度是6Mn2k, 改造為改造為cnf范式后范式后, move長度是長度是6Mn2k.改造為改造為3cnf后后, 長度增加常數(shù)倍長度增加常數(shù)倍.所以所以3SAT是是NP完全的完全的.61621, 1, 1, 1,1moveajiajiaaanjixxk 是合法窗口是合法窗口 恰當(dāng)覆蓋問題恰當(dāng)覆蓋問題(Exact Cover, EC) 有限集有限集U, 論域論域, 全集全集 子集簇子集簇F=S1, S2, Sm 是否有是否有F的兩兩不交子簇的兩兩不

31、交子簇, 其并為其并為U 例例: U=1,6, F=1,3,2,3,6,1,5,2,3,4,5,6,2,4 定理定理: EC NP. 證明證明: 非確定選擇子集簇非確定選擇子集簇, 驗證驗證. 定理定理: 3SAT PEC. 定理定理: 3SAT PEC. EC= | U的子集簇的子集簇F有不交子簇并為有不交子簇并為U 對于對于3cnf公式公式 , 構(gòu)造構(gòu)造 f() = 設(shè)設(shè) 有變量有變量x1,xn,子句子句C1,Cs, Cj有文字有文字ajk, 1 k 3 U = x1,xn C1,Cs pjk | 1 j s, 1 k 3 F 由下面的集合組成由下面的集合組成 變量子集變量子集 Ti,1

32、= xi pjk | ajk = xi xi的負(fù)文字的負(fù)文字 Ti,0 = xi pjk | ajk = xi xi的正文字的正文字 子句子集子句子集 Cj, pjk, 文字子集文字子集 pjk 可滿足可滿足 (U,F) 有恰當(dāng)覆蓋有恰當(dāng)覆蓋 原則原則: 子句子集對應(yīng)真文字子句子集對應(yīng)真文字, 變量子集對應(yīng)假文字變量子集對應(yīng)假文字, 文字子集補齊文字子集補齊 到到(U,F)歸約舉例歸約舉例 EC= | U的子集簇的子集簇F有不交子簇并為有不交子簇并為U 設(shè)設(shè)C1=(x1x2), C2=( x1 x2 x3), C3=(x2), C4=( x2x3), 則則U=x1,x2,x3 C1,C2,C3

33、,C4 p11,p12,p21,p22,p23,p31,p41,p42 F由下面的集合組成由下面的集合組成 變量子集變量子集 T1,1 = x1, p21, T1,0 = x1, p11, T2,1 = x2, p12, p41, T2,0 = x2, p22,p31, T3,1 = x3, p42, T3,0 = x3, p23, 子句子集子句子集 C1, p11, C1, p12, C4, p41, C4, p42, 文字子集文字子集 p11, p12, p41, p42, 原則原則: 子句子集對應(yīng)真文字子句子集對應(yīng)真文字, 變量子集對應(yīng)假文字變量子集對應(yīng)假文字, 文字子集補齊文字子集補齊

34、 哈密頓路徑哈密頓路徑(HP)是是NPC(3SAT PHP)HP= | G是有向圖是有向圖, 有從有從s到到t的哈密頓路徑的哈密頓路徑 任任取取3cnf公式公式 = (a1 b1 d1) (ak bk dk), 不妨設(shè)有不妨設(shè)有k個子句個子句c1, ck, n個變量個變量x1, xn,構(gòu)造構(gòu)造 f( ) = 使得使得 可滿足可滿足 G有從有從s到到t的的HP一般從一般從3cnf公式構(gòu)造圖有公式構(gòu)造圖有 變量構(gòu)件變量構(gòu)件,子句構(gòu)件子句構(gòu)件, 聯(lián)接聯(lián)接構(gòu)件構(gòu)件變量構(gòu)件和子句構(gòu)件變量構(gòu)件和子句構(gòu)件變量變量xi表示為一個鉆石結(jié)構(gòu)表示為一個鉆石結(jié)構(gòu)xicj子句子句cj表示為一個節(jié)點表示為一個節(jié)點圖圖G的

35、總體結(jié)構(gòu)的總體結(jié)構(gòu)對應(yīng)對應(yīng)n個變量個變量x1, xn, k個子句個子句c1, ck,起點起點s, 終點終點t st鉆石構(gòu)件中的水平節(jié)點鉆石構(gòu)件中的水平節(jié)點分分隔隔節(jié)節(jié)點點xi分分隔隔節(jié)節(jié)點點c1c2水平行除兩端的兩個節(jié)點外有水平行除兩端的兩個節(jié)點外有3k+1個節(jié)點個節(jié)點每個子句對應(yīng)一對節(jié)點每個子句對應(yīng)一對節(jié)點(共共2k個個)用分隔節(jié)點隔開用分隔節(jié)點隔開(k+1個個)變量與子句構(gòu)件的連接變量與子句構(gòu)件的連接xi分分隔隔節(jié)節(jié)點點cj當(dāng)子句當(dāng)子句cj含有文字含有文字xi時時添加的邊添加的邊當(dāng)子句當(dāng)子句cj含有文字含有文字 xi時時添加的邊添加的邊cjxi分分隔隔節(jié)節(jié)點點cjcj 可滿足可滿足 G有從

36、有從s到到t的哈密頓路徑的哈密頓路徑 設(shè)計思路設(shè)計思路:變量賦值變量賦值1對應(yīng)左對應(yīng)左-右式通過鉆石右式通過鉆石, 反之右左反之右左式式 cj可選一真文字處進(jìn)出一次可選一真文字處進(jìn)出一次正規(guī)路徑正規(guī)路徑xi分分隔隔節(jié)節(jié)點點cj當(dāng)子句當(dāng)子句cj含有文字含有文字xi時時添加的邊添加的邊當(dāng)子句當(dāng)子句cj含有文字含有文字 xi時時添加的邊添加的邊cjxi分分隔隔節(jié)節(jié)點點cjcjG有從有從s到到t的哈密頓路徑的哈密頓路徑 可滿足可滿足若每個鉆石都是左右式或右左式通過若每個鉆石都是左右式或右左式通過, 則稱為正規(guī)路徑則稱為正規(guī)路徑若若s到到t的哈密頓路徑是正規(guī)路徑的哈密頓路徑是正規(guī)路徑, 則公式則公式 可滿足可滿足從從s到