np完整性理論ppt課件-文庫吧在線文庫
【正文】 計(jì)算模型與直線式程序計(jì)算模型基本 相同： (1)假設(shè)所有變量取值 0或 1，即為位變量。 11 RAM模型的變形與簡(jiǎn)化 5. 判定樹 判定樹是一棵二叉樹。 12 RAM模型的變形與簡(jiǎn)化 6. 代數(shù)計(jì)算樹 ACT 以 x=(x1， x2， … ， xn)為輸入的一棵代數(shù)計(jì)算樹 T是一棵 二叉樹，且： (1)每個(gè)葉結(jié)點(diǎn)表示一個(gè)輸出結(jié)果 YES或 NO。 14 圖靈機(jī) 1. 多帶圖靈機(jī) 15 圖靈機(jī) 1. 多帶圖靈機(jī) 根據(jù)有限狀態(tài)控制器的當(dāng)前狀態(tài)及每個(gè)讀寫頭讀到的帶符號(hào)， 圖靈機(jī)的一個(gè)計(jì)算步可實(shí)現(xiàn)下面 3個(gè)操作之一或全部。 (5)q0是初始狀態(tài) 。 與 RAM模型類似，圖靈機(jī)既可作為語言接受器，也可作為計(jì)算函數(shù)的裝置。 其中的 n通常為問題 A的規(guī)模 (大小 )。 20 問題變換與計(jì)算復(fù)雜性歸約 通過問題變換獲得問題的計(jì)算時(shí)間下界的例子 ： (1)判別函數(shù)問題：給定 n個(gè)實(shí)數(shù) ，計(jì)算其判別函數(shù) 。x1,x2,… ,xk)， 當(dāng)它屬于 δ 的定義域時(shí)， Q?(T?{L，R， S})k中有惟一的一個(gè) 子集 δ(q。 該問題的輸入是一個(gè)有 n個(gè)頂點(diǎn)的無向圖 G=(V， E)和一個(gè)整數(shù) k。 ||w)( 2nO 在算法的第二階段中，非確定性地選擇 V的一個(gè) k元子集 V’?V。（ 證明見書本） 例如 (哈密頓回路問題 )：一個(gè)無向圖 G含有哈密頓回路嗎 ? 無向圖 G的哈密頓回路是通過 G的每個(gè)頂點(diǎn)恰好一次的簡(jiǎn)單回路 。但前提是：要有第一個(gè) NP完全問題 L。 問題描述： 給定一個(gè)合取范式 α ， 判定它是否可滿足。 通過 3SAT∝ pCLIQUE來證明 CLIQUE是 NP難的，從而證明團(tuán)問題是 NP完全的。 例如，若 S={1， 4，16， 64， 256， 1040， 1041， 1093， 1284， 1344}且 t=3754， 則子集 S’={1， 16， 64， 256， 1040， 1093， 1284}是一個(gè)解。驗(yàn)證算法要驗(yàn)證這 n個(gè)頂點(diǎn)組成的序列是圖 G的一條回路，且經(jīng)過每個(gè)頂點(diǎn)一次。 問題描述： 給定一個(gè)無向完全圖 G=(V， E)及定義在 V?V上的一個(gè)費(fèi)用函數(shù) c和一個(gè)整數(shù) k， 判定 G是否存在經(jīng)過 V中各頂點(diǎn)恰好一次的回路，使得該回路的費(fèi)用不超過 k。哈密頓回路問題可在多項(xiàng)式時(shí)間內(nèi)變換為旅行售貨員問題。Si i37 哈密頓回路問題 （ HAMCYCLE） 證明思路： 首先，已知哈密頓回路問題是一個(gè) NP類問題。 其次，通過 CLIQUE∝ pVERTEXCOVER來證明頂點(diǎn)覆蓋問題是 NP難的。 xx ))()(( 3213221 xxxxxxx ????321 xxx ?33 3元合取范式的可滿足性問題 （ 3SAT） 證明思路： 3SAT∈NP 是顯而易見的。 對(duì)于任給的布爾變量 ， … ， 的 0，1賦值 ， 容易在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證相應(yīng)的 … 的取值是 否為 1。 設(shè) ， 是 2個(gè)語言。因此，整個(gè)算法的時(shí)間復(fù)雜性為 。 } 1log2 ?? kn25 P類與 NP類語言 接受該語言 CLIQUE的 非確定性算法 ：用非確定性選擇指令選出包含 k個(gè)頂點(diǎn)的候選頂點(diǎn)子集 V， 然后確定性地檢查該子集是否是團(tuán)問題的一個(gè)解。 在圖靈機(jī)計(jì)算模型中，移動(dòng)函數(shù) δ 是單值的 ，即對(duì)于 Q?Tk中的每一個(gè)值，當(dāng)它屬于 δ 的定義域時(shí)， Q?(T?{L， R， S})k中只有惟一的值與之對(duì)應(yīng)，稱這種圖靈機(jī)為 確定性圖靈機(jī) ，簡(jiǎn)記為DTM(Deterministic Turing Machine)。 )log( nn? (2)最接近點(diǎn)對(duì)問題：給定平面上 n個(gè)點(diǎn)，找出這 n個(gè)點(diǎn)中距離最近的 2個(gè)點(diǎn)。這樣就可以將一個(gè)問題的計(jì)算復(fù)雜性歸結(jié)為另一個(gè)問題的計(jì)算復(fù)雜性，從而實(shí)現(xiàn)問題的計(jì)算復(fù)雜性歸約。 )(nT))(( 2 nTO18 問題變換與計(jì)算復(fù)雜性歸約 具體地說 ， 假設(shè)有 2個(gè)問題 A和 B， 將 問題 A變換為問題 B是指： (1)將問題 A的輸入變換為問題 B的適當(dāng)輸入 。 16 圖靈機(jī) 1. 多帶圖靈機(jī) 圖靈機(jī) M的時(shí)間復(fù)雜性 T(n)是它處理所有長(zhǎng)度為 n的輸入所需的最大計(jì)算步數(shù)。 k帶圖靈機(jī)可形式化地描述為一個(gè) 7元組 (Q
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1