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

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

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

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

4、)掃描帶掃描帶,如果在如果在1的右邊發(fā)現(xiàn)的右邊發(fā)現(xiàn)0,則拒絕則拒絕. 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的運(yùn)行時間是的運(yùn)行時間是O(n2). 時間復(fù)雜性類時間復(fù)雜性類 定義定義: 對于函數(shù)對于函數(shù)t:NN, 時間復(fù)雜性類時間復(fù)雜性類 TIME( t(n) ) 定義為定義為: TIME(t

5、(n) = L | 存在存在O(t(n)時間時間TM判定判定L 因?yàn)橐驗(yàn)镸1是時間是時間O(n2)圖靈機(jī)圖靈機(jī), 所以所以A=0k1k:k 0 TIME(n2). 是否存在更快的是否存在更快的TM判定判定A呢呢? 圖靈機(jī)圖靈機(jī)M2 M2=“對輸入串對輸入串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

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

7、 TIME(o(nlogn) 非正則語言非正則語言 0k1k | k 0 TIME(o(nlogn) 二二. 不同模型的時間復(fù)雜度比較不同模型的時間復(fù)雜度比較 單帶與多帶單帶與多帶 確定與非確定確定與非確定 單帶與多帶運(yùn)行時間比較單帶與多帶運(yùn)行時間比較 0k1k | k 0 有有O(n)時間雙帶圖靈機(jī)時間雙帶圖靈機(jī) 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,就

8、接受就接受.” 定理定理:設(shè)函數(shù)設(shè)函數(shù)t(n) n, 則每個則每個t(n)時間多帶時間多帶TM 和某個和某個O(t2(n)時間單帶時間單帶TM等價等價. 0k1k|k 0的的O(n)時間雙帶圖靈機(jī)時間雙帶圖靈機(jī) q0q1 qaq2 R R $ 00 R R0 L R1 L R1 L R $ NTM的運(yùn)行時間的運(yùn)行時間 定義定義: 對非確定型判定器對非確定型判定器N, 其運(yùn)行時間其運(yùn)行時間f(n)是是 在在所有所有長為長為n的輸入上的輸入上, 所有所有分支的最大步數(shù)分支的最大步數(shù). . . . f(n) 接受接受/拒絕拒絕 . . . f(n) . . . . . . . . . TMNTM 定

9、理定理: 設(shè)設(shè)t(n) n, 則每個則每個 時間時間t(n)NTM 都有一等價的都有一等價的 時間時間2O(t(n)TM. NTIME(t(n) TIME (2O(t(n) 三三. P與與NP 多項(xiàng)式時間多項(xiàng)式時間 運(yùn)行時間相差多項(xiàng)式可以認(rèn)為是小的運(yùn)行時間相差多項(xiàng)式可以認(rèn)為是小的 相差指數(shù)可以認(rèn)為是大的相差指數(shù)可以認(rèn)為是大的. 例如例如:n3與與2n,對于對于n=1000. 有關(guān)有關(guān)素性測試素性測試: Prime= p | p是素?cái)?shù)是素?cái)?shù) 如何編碼如何編碼? 一進(jìn)制一進(jìn)制,二進(jìn)制二進(jìn)制,十進(jìn)制十進(jìn)制? 典型的指數(shù)時間算法來源于典型的指數(shù)時間算法來源于蠻力搜索蠻力搜索. 有時通過深入理解問題可以

10、避免蠻搜有時通過深入理解問題可以避免蠻搜. 2001年年P(guān)rime被證明存在被證明存在多項(xiàng)式時間算法多項(xiàng)式時間算法. P類類 定義定義:P是是單帶確定單帶確定TM在在 多項(xiàng)式時間內(nèi)可判定的問題多項(xiàng)式時間內(nèi)可判定的問題,即即 P = k TIME(nk) P類的重要性在于類的重要性在于: 1) 對于所有與單帶確定對于所有與單帶確定TM等價的等價的模型模型,P不變不變. 2) P大致對應(yīng)于在計(jì)算機(jī)上大致對應(yīng)于在計(jì)算機(jī)上實(shí)際可解實(shí)際可解的問題的問題. 研究的核心是一個問題是否屬于研究的核心是一個問題是否屬于P類類. NP類類 NTIME(t(n)=L|L可被可被O(t(n)時間時間NTM判定判定.

11、定義定義:NP是是單帶非確定單帶非確定TM在在 多項(xiàng)式時間內(nèi)可判定的問題多項(xiàng)式時間內(nèi)可判定的問題,即即 NP = k NTIME(nk) EXP = k TIME(2(nk) P NP EXP P EXP 一些一些P問題問題 有些問題初看起來不屬于有些問題初看起來不屬于P 求最大公因子求最大公因子: 歐幾里德算法歐幾里德算法, 輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法 模模p指數(shù)運(yùn)算指數(shù)運(yùn)算ab mod p 素性測試素性測試 等等等等 以增加空間復(fù)雜性來減小時間復(fù)雜性以增加空間復(fù)雜性來減小時間復(fù)雜性 上下文無關(guān)上下文無關(guān)語言語言 有有O(n3)判定器判定器 快速驗(yàn)證快速驗(yàn)證 HP = |G是包含從是包含從s到到t

12、的的 哈密頓路徑哈密頓路徑的有向圖的有向圖 CLIQUE=|G是有是有k團(tuán)的無向圖團(tuán)的無向圖 目前目前沒有快速算法沒有快速算法,但其但其成員成員是可以快速驗(yàn)證的是可以快速驗(yàn)證的. 注意注意:HP的的補(bǔ)補(bǔ)可能可能不是可以快速驗(yàn)證的不是可以快速驗(yàn)證的. 快速驗(yàn)證的特點(diǎn)快速驗(yàn)證的特點(diǎn): 1. 只需要對語言中的串能快速驗(yàn)證只需要對語言中的串能快速驗(yàn)證. 2. 驗(yàn)證需要借助額外的信息驗(yàn)證需要借助額外的信息:證書證書,身份證身份證. NP問題問題 團(tuán)團(tuán):無向圖的完全子圖無向圖的完全子圖(所有節(jié)點(diǎn)都有邊相連所有節(jié)點(diǎn)都有邊相連). CLIQUE=|G是有是有k團(tuán)的無向圖團(tuán)的無向圖 定理定理: CLIQUE N

13、P. N=“對于對于輸入輸入,這里這里G是一個圖是一個圖: 1)非確定地選擇非確定地選擇G中中k個節(jié)點(diǎn)的子集個節(jié)點(diǎn)的子集c. 2)檢查檢查G是否包含連接是否包含連接c中節(jié)點(diǎn)的所有邊中節(jié)點(diǎn)的所有邊. 3)若是若是,則接受則接受;否則否則,拒絕拒絕.” 哈密頓路徑問題哈密頓路徑問題HP NP HP=|G是包含從是包含從s到到t的的 哈密頓路徑哈密頓路徑的有向圖的有向圖 P時間內(nèi)判定時間內(nèi)判定HP的的NTM: N1=“對于輸入對于輸入: 1)非確定地選非確定地選G的所有節(jié)點(diǎn)的排列的所有節(jié)點(diǎn)的排列p1,pm. 2)若若s=p1,t=pm,且對每個且對每個i, (pi,pi+1)是是G的邊的邊, 則接受

14、則接受;否則拒絕否則拒絕.” P與與NP P=成員資格可以成員資格可以快速快速判定判定的語言類的語言類. NP=成員資格可以成員資格可以快速快速驗(yàn)證驗(yàn)證的語言類的語言類. 顯然有顯然有 P NP 但是否有但是否有 P=NP ? 看起來難以想象看起來難以想象, 但是現(xiàn)在沒有發(fā)現(xiàn)反例但是現(xiàn)在沒有發(fā)現(xiàn)反例. P NP P=NP 當(dāng)代數(shù)學(xué)與當(dāng)代數(shù)學(xué)與 理論計(jì)算機(jī)理論計(jì)算機(jī) 共同的難題共同的難題. NP完全性的定義完全性的定義 SAT是是NP完全問題完全問題 一些一些NP完全問題完全問題 NP完全性完全性 Cook和和Levin于于70s證明證明 NP中中某些問題某些問題的復(fù)雜性與的復(fù)雜性與 整個整個N

15、P類類的復(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)可由此說明一個可由此說明一個問題目前還沒有問題目前還沒有快速算法快速算法. 合取范式合取范式 布爾變量布爾變量: 取值為取值為1和和0( T, F )的變量的變量. 布爾運(yùn)算布爾運(yùn)算: AND( ),OR ( ),NOT ( ). 布爾公式布爾公式. 例例: 1 = ( ( x) y ) ( x (

16、 z) ), 2 = ( x) x 稱稱 可滿足可滿足, 若存在布爾變量的若存在布爾變量的0,1賦值使得賦值使得 =1. 不可滿足不可滿足 永真永真 合取范式合取范式: 正負(fù)文字正負(fù)文字(變量變量,變量的非變量的非) 子句子句(文字的或文字的或) ( x1) x2 ( x3) (x2 ( x3) x4 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 = | 是可滿

17、足是可滿足的布爾公式的布爾公式 二元可滿足性問題二元可滿足性問題: 2SAT = | 是可滿足的是可滿足的2cnf 三元可滿足性問題三元可滿足性問題: 3SAT = | 是可滿足的是可滿足的3cnf 二元可滿足問題二元可滿足問題2SAT P 1. 當(dāng)當(dāng)2cnf中有子句是單文字中有子句是單文字x, 則反復(fù)執(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) (

18、 x3 x5) ( x4x5) ( x3 x4) (x3x2) ( x2) (x3 x4) ( x3 x5) ( x4x5) ( x3 x4) (x3 x4) ( x3 x5) ( x4x5) ( x3 x4) 2. 若無單文字子句若無單文字子句, 則任選變量賦真則任選變量賦真/假值各清洗一次假值各清洗一次 若兩次都清洗失敗若兩次都清洗失敗, 則回答不可滿足則回答不可滿足. x3: (x5) ( x4x5) (x4) ( x4) (x4) 失敗失敗 x3: (x4) ( x4x5) ( x5) 成功成功 3. 若成功清洗后有子句剩下若成功清洗后有子句剩下, 則則繼續(xù)繼續(xù)2. 否則否則, 回答可

19、滿足回答可滿足. 注注: 見見S習(xí)題習(xí)題7.23, 作者給出的答案與清洗算法作者給出的答案與清洗算法等價等價 多項(xiàng)式時間映射歸約與多項(xiàng)式時間映射歸約與C-L定理定理 Cook-Levin定理定理: SAT P P=NP. 定義定義:多項(xiàng)式時間多項(xiàng)式時間可計(jì)算函數(shù)可計(jì)算函數(shù)f: *. 定義定義:稱稱A可可多項(xiàng)式時間多項(xiàng)式時間映射歸約映射歸約到到B (A PB), 若存在若存在多項(xiàng)式時間多項(xiàng)式時間可計(jì)算函數(shù)可計(jì)算函數(shù)f: *, w*, w A f(w) B. 函數(shù)函數(shù)f稱為稱為A到到B的的多項(xiàng)式時間多項(xiàng)式時間歸約歸約. 通俗地說通俗地說: f 將將A的實(shí)例編碼轉(zhuǎn)換為的實(shí)例編碼轉(zhuǎn)換為B的實(shí)例編碼的實(shí)

20、例編碼. Cook-Levin定理定理: 對任意對任意A NP都有都有A P SAT. 定理定理1: 若若 A P B, 且且 B P, 則則 A P. 注注: 定理定理1說明說明, 若若SAT P, 則則 NP = P . 多項(xiàng)式時間映射歸約的作用多項(xiàng)式時間映射歸約的作用 輸入輸入w f f(w) M y/n w*, w A f(w) B. 定理定理1: 若若 A P B, 且且 B P, 則則 A P. 證明證明: 設(shè)設(shè) f: *是是A到到B的的P時間歸約時間歸約, B有有P時間判定器時間判定器M, 則則 N=“輸入輸入w, 計(jì)算計(jì)算M(f(w), 輸出輸出M的運(yùn)行結(jié)果的運(yùn)行結(jié)果” 在多項(xiàng)

21、式時間內(nèi)判定在多項(xiàng)式時間內(nèi)判定A. 利用利用f和和B的判定的判定器器 構(gòu)造構(gòu)造A的判定器的判定器 定理定理: 3SAT P CLIQUE 3SAT = | 是可滿足的是可滿足的3cnf公式公式 CLIQUE = | G是有是有k團(tuán)的無向圖團(tuán)的無向圖 . 證明證明:設(shè)設(shè) =(a1 b1 c1) (ak bk ck),有有k個子句個子句. f( ) = , G有有k組節(jié)點(diǎn)組節(jié)點(diǎn),每組每組3個個; 同組同組節(jié)點(diǎn)無邊相連節(jié)點(diǎn)無邊相連, 相反標(biāo)記相反標(biāo)記無邊相連無邊相連. f(x1 x1 x2) (x1 x2 x2) (x1 x2 x2) = x1 x1 x2 x1 x2 x2 x1 x2 x2 需證需

22、證:3SAT (G,k) CLIQUE , 3SATf( ) CLIQUE () 3SAT 變量賦值變量賦值(x1=0, x2=1)使得使得 =1 k團(tuán)團(tuán)(每組挑一個真頂點(diǎn)得到每組挑一個真頂點(diǎn)得到k團(tuán)團(tuán), 非同組非相反非同組非相反) f( ) () CLIQUE. x1 x1 x2 x1 x2 x2 x1 x2 x2 NP完全性完全性 定義定義:語言語言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. 定

23、理定理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. 利用利用f和和B的判定的判定器器 構(gòu)造構(gòu)造A的判定器的判定器 Cook-Levin定理的證明步驟定理的證明步驟 定義定義:語言語言B稱為稱為NP完全的完全的(NPC),若它滿足若它滿足: 1) B NP; 2) A NP, 都有都有A PB. Cook-Levin定理定理:

24、SAT是是NP完全問題完全問題. 證明步驟證明步驟: 1. SAT NP(?), 2. A NP, A P SAT (?) N=“對于輸入對于輸入, 是一個布爾公式是一個布爾公式: 1)非確定地非確定地選擇選擇 所有變量的賦值所有變量的賦值T. 2)檢查在賦值檢查在賦值T下是否下是否 =1 3)若是若是,則接受則接受;否則否則,拒絕拒絕.” SAT是是NP完全問題完全問題 要證明要證明: 1) SAT NP. 2) A NP, 都有都有 A P SAT. 思想思想: 將字符串對應(yīng)到布爾公式將字符串對應(yīng)到布爾公式 利用接受的形式定義利用接受的形式定義. 過程過程: 任取任取A NP, 設(shè)設(shè)N是是

25、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 起始格局起始格局 第第2個格局個格局 第第nk個格局個格局 窗口窗口 能填好畫面能填好畫面: 第一行是起始格局第一行是起始格局 上一行能產(chǎn)生上一行能產(chǎn)生(或等于或等于)下一行下一行 畫面中有接受狀態(tài)畫面中有接受狀態(tài) 構(gòu)造布爾公式構(gòu)造布爾公式f(w) 能能填好畫

26、面填好畫面f(w)可滿足可滿足 f(w)=, = cellstartmoveaccept . 對于任意賦值對于任意賦值: 1. cell =1 每格有且只有每格有且只有一個符號一個符號; 2. start =1 第一行是起始格局第一行是起始格局; 3. accept =1 表格中有接受狀態(tài)表格中有接受狀態(tài); 4. move=1 每行由上一行格局每行由上一行格局產(chǎn)生產(chǎn)生. w, w A SAT 即即 A m SAT 若若|是是|w|的多項(xiàng)式的多項(xiàng)式, 則有則有A P SAT 構(gòu)造構(gòu)造 cell )( , ,1 celltjisji ts sji snji xxx k 長長O(n2k) cell

27、= 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 , jijijijijiji jijiji xxxxxx xxx 構(gòu)造構(gòu)造 start # , ,# ,start k n wq xxxx 1 312111 10 長長O(nk) start = 1 第一行是起始格局第一行是起始格局; 構(gòu)造構(gòu)造 accept accept , , acceptqji nji x k 1 長長O(n2k) accept =

28、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是任意符號是任意符號,則則 aq1b q2ac aq1b aeq2 daq1 dae asb asb sta stq2 bsa csa abt ast aq1b aaq1 aq1b q1aq1 合法合法 窗口窗口 非法非法 窗口窗口 61 621 , 1, 1, 1, ,

29、 ,1 moveajiaji aaa nji xx k 是合法窗口是合法窗口 長長 O(n2k) A PSAT, SAT是是NPC 61 621 , 1, 1, 1, , ,1 moveajiaji aaa nji xx k 是合法窗口是合法窗口 )( , ,1 celltjisji ts sji s nji xxx k # , ,# ,start k n wq xxxx 1 312111 10 accept , , acceptqji nji x k 1 f(w) = w A SAT, | = O(n2k) = cellstartmoveaccept . 推論推論:3SAT是是NP完全的完全

30、的 只需將前面的只需將前面的 改造為改造為3cnf公式公式. = cellstartmove accept. # , ,# ,start k n wq xxxx 1 312111 10 accept , , acceptqji nji x k 1 )( , ,1 celltjisji ts sji s nji xxx k 任取變量賦值任取變量賦值 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的改造的改造 分配律分配律

31、 (a b) c = (a 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完全的完全的. 61 621 , 1, 1, 1, , ,1 moveajiaji aaa nji xx k 是合法窗口是合法窗口 恰當(dāng)覆蓋問題恰當(dāng)覆蓋問題(Exact Cover, EC) 有限集有限集U, 論域論域, 全集全集 子集簇子集簇F=S1

32、, S2, Sm 是否有是否有F的兩兩不交子簇的兩兩不交子簇, 其并為其并為U 例例: U=1,6, F=1,3,2,3,6,1,5,2,3,4,5,6,2,4 定理定理: EC NP. 證明證明: 非確定選擇子集簇非確定選擇子集簇, 驗(yàn)證驗(yàn)證. 定理定理: 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 由下面的

33、集合組成由下面的集合組成 變量子集變量子集 Ti,1 = 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)假文字, 文字子集補(bǔ)齊文字子集補(bǔ)齊 到到(U,F)歸約舉例歸約舉例 EC= | U的子集簇的子集簇F有不交子簇并為有不交子簇并為U 設(shè)設(shè)C1=(x1x2), C2=( x1 x2 x3), C3=(x2), C4=( x

34、2x3), 則則U=x1,x2,x3 C1,C2,C3,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)真文字, 變量子集對

35、應(yīng)假文字變量子集對應(yīng)假文字, 文字子集補(bǔ)齊文字子集補(bǔ)齊 哈密頓路徑哈密頓路徑(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)表示為一個

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

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