np完整性理論ppt課件(存儲版)
【正文】 P類與 NP類語言 NP類語言舉例 —— 無向圖的團(tuán)問題 。顯而易見，第一階段可 在時間內(nèi)完成。 多項式時間可驗證語言類 VP可定義為： 定理 85： VP=NP。 1L 1L 1L定理 86的 (2)可用來證明問題的 NP完全性。 （ 詳細(xì)證明見書本 P307～ 310） 1x kx1A 2A mA31 一些典型的 NP完全問題 部分 NP完全問題樹 32 合取范式的可滿足性問題 （ CNFSAT） 要證明 CNFSAT∈NPC ， 只要證明在 Cook定理中定義的布爾表達(dá)式 A， … ， G或者已是合取范式，或者有的雖然不是合取范式，但可以用布爾代數(shù)中的變換方法將它們化成合取范式，而且合取范式的長度與原表達(dá)式的長度只差一個常數(shù)因子。 34 團(tuán)問題 CLIQUE 證明思路： 已經(jīng)知道 CLIQUE∈NP 。 36 子集和問題 （ SUBSETSUM） 問題描述： 給定整數(shù)集合 S和一個整數(shù) t， 判定是否存在 S的一個子集 S’?S， 使得 S’中整數(shù)的和為 t。 38 旅行售貨員問題 TSP 首先，給定 TSP的一個實例 (G， c， k)， 和一個由 n個頂點(diǎn)組成的頂點(diǎn)序列。 因此， TSP∈NPC 。即HAMCYCLE∝ pTSP。 其次，通過證明 3SAT∝ pHAMCYCLE， 得出： HAMCYCLE∈NPC 。 問題描述： 給定一個無向圖 G=(V， E)和一個正整數(shù) k， 判定是否存在 V’?V， |V’|=k， 使得對于任意 (u， v)∈E 有 u∈V ’或v∈V ’。為了證明 3SAT∈NPC ，只要證明 CNFSAT∝ p 3SAT， 即合取范式的可滿足性問題可在多項式時間內(nèi)變換為 3SAT。 因此 ， SAT∈NP 。所謂語言 能在多項式時間內(nèi)變換為語言 (簡記為 ∝ p )是指存在映身 f: ，且 f滿足： (1)有一個計算 f的多項式時間確定性圖靈機(jī)； (2)對于所有 x∈ ， x∈ ， 當(dāng)且僅當(dāng) f(x)∈ 。 )( 4nO)( 4nO非確定性算法在多項式時間內(nèi)接受語言 CLIQUE， 故 CLIQUE∈NP 。算法分為 3個階段： 算法的第一階段將輸入串 wv分解，并計算出 n= ， 以及用 v表示的整數(shù) k。 23 P類與 NP類語言 P類和 NP類語言的定義： P={L|L是一個能在 多項式時間內(nèi) 被一臺 DTM所接受的語言 } NP={L|L是一個能在 多項式時間 內(nèi)被一臺 NDTM所接受的語言 } 由于一臺確定性圖靈機(jī)可看作是非確定性圖靈機(jī)的特例，所以可在多項式時間內(nèi)被確定性圖靈機(jī)接受的語言也可在多項式時間內(nèi)被非確定性圖靈機(jī)接受。 在元素惟一性問題中，將每一個實數(shù) ， 1≤ i≤n ， 變換為平面上的點(diǎn) ( ， 0)， 1≤ i≤n ， 則元素惟一性問題可以在線性時間內(nèi)變換為最接近點(diǎn)對問題。 19 問題變換與計算復(fù)雜性歸約 命題 1(計算時間下界歸約 )：若已知問題 A的計算時間下界為 T(n)， 且問題 A是 τ(n) 可變換到問題 B， 即 A∝ τ(n) B， 則 T(n)O(τ(n)) 為問題 B的一個計算時間下界。 (2)解出問題 B。如果對某個長度為 n的輸入，圖靈機(jī)不停機(jī)，T(n)對這個 n值無定義。 (2)T是有限個帶符號的集合。 代數(shù)判定樹 T是一棵二叉樹，且 (1)每個葉結(jié)點(diǎn)表示輸出結(jié)果 YES或 NO。下圖是對 a， b， c三個數(shù)進(jìn)行排序的一棵判定樹。 例如，要表示一個有 100個頂點(diǎn)的圖中從頂點(diǎn) v到其余各頂點(diǎn) 間有沒有邊相連，可以用 100位的一個位向量表示。 每條指令耗費(fèi)一個單位時間。 (2)2個實數(shù)間的比較 (， ≤ ， =， ≠ ， ≥ ， )。 RASP指令用整數(shù)進(jìn)行編碼。如果一個 RAM程序 P讀了字符串 S及結(jié)束標(biāo)志符 0后，在輸出 帶的第一格輸出一個 1并停機(jī)，就說程序 P接受字符串 S?？梢詫? 這種映射關(guān)系作 2種不同的解釋。 標(biāo)準(zhǔn)二：對數(shù)耗費(fèi)標(biāo)準(zhǔn) 對數(shù)耗費(fèi)標(biāo)準(zhǔn)是基于這樣的假定，即執(zhí)行一條指令的耗費(fèi) 與以二進(jìn)制表示的指令的操作數(shù)長度成比例。其中 k是一個常數(shù)因子。 優(yōu)點(diǎn)：能夠方便處理實數(shù)； 適合于用 FORTRAN， PASCAL等高級語言寫的算法。 除了下列 2點(diǎn)外，該
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1