np完整性理論ppt課件(參考版)
2025-05-08 18:18本頁(yè)面
【正文】 。 因此， TSP∈NPC 。即HAMCYCLE∝ pTSP。 其次，旅行售貨員問(wèn)題與哈密頓回路問(wèn)題有著密切的聯(lián)系。另外，將每條邊的費(fèi)用加起來(lái)，并驗(yàn)證所得的和不超過(guò) k。 38 旅行售貨員問(wèn)題 TSP 首先，給定 TSP的一個(gè)實(shí)例 (G， c， k)， 和一個(gè)由 n個(gè)頂點(diǎn)組成的頂點(diǎn)序列。 其次，通過(guò)證明 3SAT∝ pHAMCYCLE， 得出： HAMCYCLE∈NPC 。 ?? 39。 證明思路： 首先，對(duì)于子集和問(wèn)題的一個(gè)實(shí)例 S， t， 給定一個(gè) “ 證書(shū) ” S’， 要驗(yàn)證 t= 是否成立，顯然可在多項(xiàng)式時(shí)間內(nèi)完成。 36 子集和問(wèn)題 （ SUBSETSUM） 問(wèn)題描述： 給定整數(shù)集合 S和一個(gè)整數(shù) t， 判定是否存在 S的一個(gè)子集 S’?S， 使得 S’中整數(shù)的和為 t。 問(wèn)題描述： 給定一個(gè)無(wú)向圖 G=(V， E)和一個(gè)正整數(shù) k， 判定是否存在 V’?V， |V’|=k， 使得對(duì)于任意 (u， v)∈E 有 u∈V ’或v∈V ’。 因?yàn)閷?duì)于給定的圖 G和正整數(shù) k以及一個(gè) “ 證書(shū) ” V’， 驗(yàn)證 |V’|=k， 然后對(duì)每條邊 (u， v)∈E ，檢查是否有 u∈V ’或 v∈V ’， 顯然可在多項(xiàng)式時(shí)間內(nèi)完成。 問(wèn)題描述： 給定一個(gè)無(wú)向圖 G=(V， E)和一個(gè)正整數(shù) k， 判定圖 G是否包含一個(gè) k團(tuán)，即是否存在， V’?V，|V’|=k， 且對(duì)任意 u， w∈V ’有 (u， w)∈E 。 34 團(tuán)問(wèn)題 CLIQUE 證明思路： 已經(jīng)知道 CLIQUE∈NP 。為了證明 3SAT∈NPC ，只要證明 CNFSAT∝ p 3SAT， 即合取范式的可滿(mǎn)足性問(wèn)題可在多項(xiàng)式時(shí)間內(nèi)變換為 3SAT。例如： 就是一個(gè)合取范式，而 就不是合取范式。 如果一個(gè)布爾表達(dá)式是一些因子和之積，則稱(chēng)之為合取范式，簡(jiǎn)稱(chēng) CNF(Conjunctive Normal Form)。 （ 詳細(xì)證明見(jiàn)書(shū)本 P307～ 310） 1x kx1A 2A mA31 一些典型的 NP完全問(wèn)題 部分 NP完全問(wèn)題樹(shù) 32 合取范式的可滿(mǎn)足性問(wèn)題 （ CNFSAT） 要證明 CNFSAT∈NPC ， 只要證明在 Cook定理中定義的布爾表達(dá)式 A， … ， G或者已是合取范式，或者有的雖然不是合取范式，但可以用布爾代數(shù)中的變換方法將它們化成合取范式，而且合取范式的長(zhǎng)度與原表達(dá)式的長(zhǎng)度只差一個(gè)常數(shù)因子。 因此 ， SAT∈NP 。 1x kx1A mA ix1A 2A mAiA SAT∈NP 是很明顯的 。 30 Cook定理 定理 87(Cook定理 )： 布爾表達(dá)式的可滿(mǎn)足性問(wèn)題 SAT是 NP完全的。 1L 1L 1L定理 86的 (2)可用來(lái)證明問(wèn)題的 NP完全性。所謂語(yǔ)言 能在多項(xiàng)式時(shí)間內(nèi)變換為語(yǔ)言 (簡(jiǎn)記為 ∝ p )是指存在映身 f: ，且 f滿(mǎn)足： (1)有一個(gè)計(jì)算 f的多項(xiàng)式時(shí)間確定性圖靈機(jī)； (2)對(duì)于所有 x∈ ， x∈ ， 當(dāng)且僅當(dāng) f(x)∈ 。所有 NP完全語(yǔ)言構(gòu)成的語(yǔ)言類(lèi)稱(chēng)為 NP完全語(yǔ)言類(lèi) ，記為 NPC。可用語(yǔ)言 HAMCYCLE 定義該問(wèn)題如下： HAMCYCLE={G|G含有哈密頓回路 } 27 NP完全問(wèn)題 ? 多項(xiàng)式時(shí)間變換 ? Cook定理 28 多項(xiàng)式時(shí)間變換 定義： 語(yǔ)言 L是 NP完全的當(dāng)且僅當(dāng) (1)L∈NP ； (2)對(duì)于所有 L’∈NP 有 L’ ∝ p L。 多項(xiàng)式時(shí)間可驗(yàn)證語(yǔ)言類(lèi) VP可定義為： 定理 85： VP=NP。 )( 4nO)( 4nO非確定性算法在多項(xiàng)式時(shí)間內(nèi)接受語(yǔ)言 CLIQUE， 故 CLIQUE∈NP 。這顯然可以在 時(shí)間內(nèi)完成。 算法的第三階段是確定性地檢查 V’的團(tuán)性質(zhì)。顯而易見(jiàn)，第一階段可 在時(shí)間內(nèi)完成。算法分為 3個(gè)階段： 算法的第一階段將輸入串 wv分解，并計(jì)算出 n= ， 以及用 v表示的整數(shù) k。因此，團(tuán)問(wèn)題可表示為語(yǔ)言： CLIQUE={wv|w， v∈{0 ， 1}*， 以 w為鄰接矩陣的圖 G有一個(gè) k頂點(diǎn)的團(tuán)，其中 v是 k的二進(jìn)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1