np完整性理論ppt課件(完整版)
【正文】 ， T， I， δ ， b， q0，qf)， 其中 : (1)Q是有限個(gè)狀態(tài)的集合。 由此引出另一個(gè)稱為代數(shù)判定樹(shù)的計(jì)算模型。每一次比較耗費(fèi)一個(gè)單位時(shí) 間。 10 RAM模型的變形與簡(jiǎn)化 4. 位向量運(yùn)算 (Bit Vector Operations) 若在直線式程序計(jì)算模型中，假設(shè)所有變量均為位向量，而 且所用的運(yùn)算均為位操作指令，則得到位向量運(yùn)算計(jì)算模型。 經(jīng)過(guò)對(duì) RAM模型的簡(jiǎn)化，得到直線式程序的指令系統(tǒng)如下： x←y+z x←y z x←y*z x←y/z x←i 其中 x， y和 z是符號(hào)地址 (或變量 )，而 i是常數(shù)。 (1)算術(shù)運(yùn)算 +，－，／。第一個(gè)寄存器存放操作碼的編碼，第二個(gè)寄存器存放地址。 然后在第 n+1個(gè)方格中放入 0，作為輸入串的結(jié)束標(biāo) 志符。 解釋一：把 RAM程序看成是計(jì)算一個(gè)函數(shù) 若一個(gè) RAM程序 P總是從輸入帶前 n個(gè)方格中讀入 n個(gè)整數(shù) x1， x2， … ， xn， 并且在輸出帶的第一個(gè)方格上輸出一個(gè)整數(shù) y 后停機(jī)，那么就說(shuō)程序 P計(jì)算了函數(shù) f(x1， x2， … ， xn)=y 解釋二：把 RAM程序當(dāng)作一個(gè)語(yǔ)言接受器。在 RAM計(jì)算模型下， 假定一個(gè)寄存器可存放一個(gè)任意大小的整數(shù)?？臻g復(fù)雜性的情況也是類似的。 8 RAM模型的變形與簡(jiǎn)化 2. 直線式程序 對(duì)于許多問(wèn)題，所設(shè)計(jì)的 RAM程序中的轉(zhuǎn)移指令僅用于重復(fù) 一組指令，而且重復(fù)的次數(shù)與問(wèn)題的輸入規(guī)模 n成比例。 (2)所用的運(yùn)算是邏輯運(yùn)算而不是算術(shù)運(yùn)算。它的每個(gè)內(nèi)結(jié)點(diǎn)表示一個(gè)形如 x∶y 的 比較。 (2)每個(gè)單兒子內(nèi)部結(jié)點(diǎn) (簡(jiǎn)單結(jié)點(diǎn) )v表示下列形式運(yùn)算指令： op 或 op 或 其中， 和 分別是結(jié)點(diǎn) v在樹(shù) T中的祖先結(jié)點(diǎn) v1和 v2處得到 的結(jié)果值，或是 x的分量； op∈{+ ，－， /}； c是一個(gè)常數(shù)。 (1)改變有限狀態(tài)控制器中的狀態(tài)。 (6)qf是終止 (或接受 )狀態(tài) 。 17 圖靈機(jī)模型與 RAM模型的關(guān)系 圖靈機(jī)模型與 RAM模型的關(guān)系是指同一問(wèn)題在這 2種不同計(jì)算模型下的復(fù)雜性之間的關(guān)系。 當(dāng) τ(n) 為 n的多項(xiàng)式時(shí)，稱問(wèn)題 A可在多項(xiàng)式時(shí)間內(nèi)變換為問(wèn)題 B。 nxxx ,..., 21?? ?ji ji xx )( 元素惟一性問(wèn)題可以在 O(1)時(shí)間內(nèi)變換為判別函數(shù)問(wèn)題。x 1,x2,… ,xk)與之對(duì)應(yīng)。 要求判定圖 G是否包含一個(gè) k頂點(diǎn)的 完全子圖 (團(tuán) )，即判定是否存在 V’?V， |V’|=k， 且對(duì)于所有的u， v∈V ’， 有 (u， v)∈E 。 算法的第三階段是確定性地檢查 V’的團(tuán)性質(zhì)?？捎谜Z(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。 30 Cook定理 定理 87(Cook定理 )： 布爾表達(dá)式的可滿足性問(wèn)題 SAT是 NP完全的。 如果一個(gè)布爾表達(dá)式是一些因子和之積，則稱之為合取范式，簡(jiǎn)稱 CNF(Conjunctive Normal Form)。 問(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 。 證明思路： 首先，對(duì)于子集和問(wèn)題的一個(gè)實(shí)例 S， t， 給定一個(gè) “ 證書(shū) ” S’， 要驗(yàn)證 t= 是否成立，顯然可在多項(xiàng)式時(shí)間內(nèi)完成。另外，將每條邊的費(fèi)用加起來(lái)，并驗(yàn)證所得的和不超過(guò) k。 。 其次，旅行售貨員問(wèn)題與哈密頓回路問(wèn)題有著密切的聯(lián)系。 ?? 39。 因?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)完成。例如： 就是一個(gè)合取范式，而 就不是合取范式。 1x kx1A mA ix1A 2A mAiA SAT∈NP 是很明顯的 。所有 NP完全語(yǔ)言構(gòu)成的語(yǔ)言類稱為 NP完全語(yǔ)言
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1