np完整性理論ppt課件-免費閱讀
【正文】 從而，旅行售貨員問題是 NP難的。 問題描述： 給定無向圖 G=(V， E)， 判定其是否含有一哈密頓回路。 如果存在這樣的 V’， 就稱 V’為圖 G的一個大小為 k頂點覆蓋。 問題描述： 給定一個 3元 合取范式 α ， 判定它是否可滿足。 現(xiàn)在只要證明對任意的 L∈NP 有 L∝ pSAT即可 。 *11 ??L *22 ??L 1L2L 1L2L*2*1 ???1L 2L*1?29 多項式時間變換 定理 86：設(shè) L是 NP完全的，則 (1)L∈P 當(dāng)且僅當(dāng) P＝ NP； (2)若 L∝ p ， 且 ∈ NP， 則 是 NP完全的。 26 多項式時間驗證 VP={L|L∈∑* ， ∑ 為一有限字符集，存在一個多項式 p和一個多項式時間驗證算法 A(X， Y)使得對任意 X∈∑* ， X∈L 當(dāng)且僅當(dāng)存在 Y∈∑* ， |Y|≤p(|X|) 且 A(X， Y)=1}。 若輸入不具有形式 wv或 |w|不是一個平方數(shù)就拒絕該輸入。故 P ? NP。 ixix21 P類與 NP類問題 ? 非確定性圖靈機 ? P類與 NP類語言 ? 多項式時間驗證 22 非確定性圖靈機 非確定性圖靈機（ NDTM ） ：一個 k帶的非確定性圖靈機 M是一個 7元組： (Q， T， I， δ ， b， q0， qf)。 命題 2(計算時間上界歸約 )：若已知問題 B的計算時間上界為 T(n)， 且問題 A是 τ(n) 可變換到問題 B， 即 A∝ τ(n) B， 則T(n)+O(τ(n)) 是問題 A的一個計算時間上界。 (3)把問題 B的輸出變換為問題 A的正確解 。 圖靈機的空間復(fù)雜性 S(n)是它處理所有長度為 n的輸入時，在 k條帶上所使用過的方格數(shù)的總和。 (3)I是輸入符號的集合 ， I?T。 (2)每個內(nèi)部結(jié)點 v表示一個形如 fv(x1， x2， … ， xn)∶0 的 比較。 在判定樹模型下，算法的時間復(fù)雜性可用判定樹的高度衡量。若頂點 v到頂 點 vj之間有邊相連，則該位向量的第 j位為 1，否則為 0。 9 RAM模型的變形與簡化 3. 位式計算 直線式程序計算模型顯然是基于均勻耗費標(biāo)準(zhǔn)的。 (3)間接尋址 (整數(shù)地址 )。 2. RASP程序的復(fù)雜性 不管是在均勻耗費標(biāo)準(zhǔn)下，還是在對數(shù)耗費標(biāo)準(zhǔn)下， RAM程序和 RASP程序的復(fù)雜性只差一個常數(shù)因子。 5 隨機存取機 RAM 3. RAM程序的耗費標(biāo)準(zhǔn) 標(biāo)準(zhǔn)一：均勻耗費標(biāo)準(zhǔn) 在均勻耗費標(biāo)準(zhǔn)下，每條 RAM指令需要一個單位時間；每 個寄存器占用一個單位空間。1 第 8章 NP完全性理論 2 計算模型 ? 隨機存取機 RAM ? 隨機存取存儲程序機 RASP ? RAM模型的變形與簡化 ? 圖靈機 ? 圖靈機模型與 RAM模型的關(guān)系 ? 問題變換與計算復(fù)雜性歸約 3 隨機存取機 RAM 1. RAM的結(jié)構(gòu) 4 隨機存取機 RAM 2. RAM程序 一個 RAM程序定義了從輸入帶到輸出帶的一個映射。以后除特別注明， RAM程序的復(fù)雜 性將按照均勻耗費標(biāo)準(zhǔn)衡量。在一個計算模型下 T(n)時間內(nèi)完成的輸入 輸出映射可在另一個計算模型下模擬，并在 kT(n)時間內(nèi)完成。 (4)常見函數(shù)的計算，如三角函數(shù)，指數(shù)函數(shù)，對數(shù)函數(shù)等。在對數(shù) 耗費標(biāo)準(zhǔn)下，使用另一個 RAM的簡化計算模型，稱之為位式計算 (Bitwise Computation)模型。 缺點： 所需的機器字長要遠(yuǎn)大于其他模型。最大的比較次數(shù)是從根到葉的最長路徑的長度。其中， x=( x1， x2， … ， xn)是輸入， fv是一個代數(shù) 函數(shù)。 (4)b是惟一的空白符 ， b∈T I。如果某個讀寫頭無限地向右移動而不停機， S(n)也無定義。 若用 O(τ(n)) 時間能完成上述變換的第 (1)步和第 (3)步 ， 則稱問題 A是 τ(n) 時間可變換到問題 B， 且簡記為 A∝ τ(n) B。 問題的變換與問題的計算復(fù)雜性歸約的關(guān)系 ： 在命題 1和命題 2中，當(dāng) τ(n)=o(T(n)) 時，問題 A的下界歸約為問題 B的下界，問題 B的上界歸約為問題 A的上界。 與確定性圖靈機不同的是非確定性圖靈機允許移動函數(shù) δ 具有不確定性 ，即對于 Q?Tk中的每一個值 (q。 24
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1