np完整性理論ppt課件-文庫吧資料
2025-05-11 18:18本頁面
【正文】 制表示。 要求判定圖 G是否包含一個 k頂點(diǎn)的 完全子圖 (團(tuán) )，即判定是否存在 V’?V， |V’|=k， 且對于所有的u， v∈V ’， 有 (u， v)∈E 。 24 P類與 NP類語言 NP類語言舉例 —— 無向圖的團(tuán)問題 。 23 P類與 NP類語言 P類和 NP類語言的定義： P={L|L是一個能在 多項(xiàng)式時間內(nèi) 被一臺 DTM所接受的語言 } NP={L|L是一個能在 多項(xiàng)式時間 內(nèi)被一臺 NDTM所接受的語言 } 由于一臺確定性圖靈機(jī)可看作是非確定性圖靈機(jī)的特例，所以可在多項(xiàng)式時間內(nèi)被確定性圖靈機(jī)接受的語言也可在多項(xiàng)式時間內(nèi)被非確定性圖靈機(jī)接受。x 1,x2,… ,xk)中隨意選定一個值作為它的函數(shù)值。x 1,x2,… ,xk)與之對應(yīng)。 與確定性圖靈機(jī)不同的是非確定性圖靈機(jī)允許移動函數(shù) δ 具有不確定性 ，即對于 Q?Tk中的每一個值 (q。 在元素惟一性問題中，將每一個實(shí)數(shù) ， 1≤ i≤n ， 變換為平面上的點(diǎn) ( ， 0)， 1≤ i≤n ， 則元素惟一性問題可以在線性時間內(nèi)變換為最接近點(diǎn)對問題。由命題 1即知，元素惟一性問題的計算時間下界 也是判別函數(shù)問題的一個計算時間下界。 nxxx ,..., 21?? ?ji ji xx )( 元素惟一性問題可以在 O(1)時間內(nèi)變換為判別函數(shù)問題。 問題的變換與問題的計算復(fù)雜性歸約的關(guān)系 ： 在命題 1和命題 2中，當(dāng) τ(n)=o(T(n)) 時，問題 A的下界歸約為問題 B的下界，問題 B的上界歸約為問題 A的上界。 19 問題變換與計算復(fù)雜性歸約 命題 1(計算時間下界歸約 )：若已知問題 A的計算時間下界為 T(n)， 且問題 A是 τ(n) 可變換到問題 B， 即 A∝ τ(n) B， 則 T(n)O(τ(n)) 為問題 B的一個計算時間下界。 通過問題變換的技巧，可以將 2個不同問題的計算復(fù)雜性聯(lián)系在一起。 當(dāng) τ(n) 為 n的多項(xiàng)式時，稱問題 A可在多項(xiàng)式時間內(nèi)變換為問題 B。 若用 O(τ(n)) 時間能完成上述變換的第 (1)步和第 (3)步 ， 則稱問題 A是 τ(n) 時間可變換到問題 B， 且簡記為 A∝ τ(n) B。 (2)解出問題 B。 )(nT))(( 2 nTO 定理 84 對于問題 P的任何長度為 n的輸入，設(shè)求解問題 P的算法 A在 RAM模型下，不含有乘法和除法指令，且按對數(shù)耗費(fèi)標(biāo)準(zhǔn)其時間復(fù)雜性為 ，那么，算法 A在 k帶圖靈機(jī)模型 TM下的時間復(fù)雜性為 。 17 圖靈機(jī)模型與 RAM模型的關(guān)系 圖靈機(jī)模型與 RAM模型的關(guān)系是指同一問題在這 2種不同計算模型下的復(fù)雜性之間的關(guān)系。如果某個讀寫頭無限地向右移動而不停機(jī)， S(n)也無定義。如果對某個長度為 n的輸入，圖靈機(jī)不停機(jī)，T(n)對這個 n值無定義。它是從 Q?Tk的某一子集映射到 Q? (T?{L， R，S})k的函數(shù)。 (6)qf是終止 (或接受 )狀態(tài) 。 (4)b是惟一的空白符 ， b∈T I。 (2)T是有限個帶符號的集合。 (3)獨(dú)立地將任何一個或所有讀寫頭，向左移動一個方格 (L)或向右移動一個方格 (R)或停在當(dāng)前單元不動 (S)。 (1)改變有限狀態(tài)控制器中的狀態(tài)。其中， x=( x1， x2， … ， xn)是輸入， fv是一個代數(shù) 函數(shù)。 代數(shù)判定樹 T是一棵二叉樹，且 (1)每個葉結(jié)點(diǎn)表示輸出結(jié)果 YES或 NO。 1vv ff ? 2vf cfv ? 1vf 1vv ff ?1vf 2vf1vf 1vf 1vf1vf13 RAM模型的變形與簡化 7. 代數(shù)判定樹 ADT(Algebraic Decision Tree) 在代數(shù)計算樹 T中，若將所有的簡單結(jié)點(diǎn)都壓縮到其最近 的子孫分支結(jié)點(diǎn)處，并將簡單結(jié)點(diǎn)處的計算在壓縮后的分支結(jié)點(diǎn) 處同時完成，則計算結(jié)果可看作是輸入 x的一個代數(shù)函數(shù) fv(x)。 (2)每個單兒子內(nèi)部結(jié)點(diǎn) (簡單結(jié)點(diǎn) )v表示下列形式運(yùn)算指令： op 或 op 或 其中， 和 分別是結(jié)點(diǎn) v在樹 T中的祖先結(jié)點(diǎn) v1和 v2處得到 的結(jié)果值，或是 x的分量； op∈{+ ，－， /}； c是一個常數(shù)。最大的比較次數(shù)是從根到葉的最長路徑的長度。下圖是對 a， b， c三個數(shù)進(jìn)行排序的一棵判定樹。指向該結(jié) 點(diǎn)右兒子的邊相應(yīng)于 xy， 標(biāo)號為 。它的每個內(nèi)結(jié)點(diǎn)表示一個形如 x∶y 的 比較。 缺點(diǎn)： 所需的
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1