【正文】 M的時間復(fù)雜性 T(n)是它處理所有長度為 n的輸入所需的最大計算步數(shù)。這樣就可以將一個問題的計算復(fù)雜性歸結(jié)為另一個問題的計算復(fù)雜性，從而實現(xiàn)問題的計算復(fù)雜性歸約。 在圖靈機計算模型中，移動函數(shù) δ 是單值的 ，即對于 Q?Tk中的每一個值，當(dāng)它屬于 δ 的定義域時， Q?(T?{L， R， S})k中只有惟一的值與之對應(yīng)，稱這種圖靈機為 確定性圖靈機 ，簡記為DTM(Deterministic Turing Machine)。因此，整個算法的時間復(fù)雜性為 。 對于任給的布爾變量 ， … ， 的 0，1賦值 ， 容易在多項式時間內(nèi)驗證相應(yīng)的 … 的取值是 否為 1。 其次，通過 CLIQUE∝ pVERTEXCOVER來證明頂點覆蓋問題是 NP難的。哈密頓回路問題可在多項式時間內(nèi)變換為旅行售貨員問題。驗證算法要驗證這 n個頂點組成的序列是圖 G的一條回路，且經(jīng)過每個頂點一次。 通過 3SAT∝ pCLIQUE來證明 CLIQUE是 NP難的，從而證明團問題是 NP完全的。但前提是：要有第一個 NP完全問題 L。 ||w)( 2nO 在算法的第二階段中，非確定性地選擇 V的一個 k元子集 V’?V。x1,x2,… ,xk)， 當(dāng)它屬于 δ 的定義域時， Q?(T?{L，R， S})k中有惟一的一個 子集 δ(q。 其中的 n通常為問題 A的規(guī)模 (大小 )。 (5)q0是初始狀態(tài) 。 12 RAM模型的變形與簡化 6. 代數(shù)計算樹 ACT 以 x=(x1， x2， … ， xn)為輸入的一棵代數(shù)計算樹 T是一棵 二叉樹，且： (1)每個葉結(jié)點表示一個輸出結(jié)果 YES或 NO。 除了下列 2點外，該計算模型與直線式程序計算模型基本 相同： (1)假設(shè)所有變量取值 0或 1，即為位變量。其中 k是一個常數(shù)因子?？梢詫? 這種映射關(guān)系作 2種不同的解釋。 RASP指令用整數(shù)進行編碼。 每條指令耗費一個單位時間。下圖是對 a， b， c三個數(shù)進行排序的一棵判定樹。 (2)T是有限個帶符號的集合。 (2)解出問題 B。 在元素惟一性問題中，將每一個實數(shù) ， 1≤ i≤n ， 變換為平面上的點 ( ， 0)， 1≤ i≤n ， 則元素惟一性問題可以在線性時間內(nèi)變換為最接近點對問題。算法分為 3個階段： 算法的第一階段將輸入串 wv分解，并計算出 n= ， 以及用 v表示的整數(shù) k。所謂語言 能在多項式時間內(nèi)變換為語言 (簡記為 ∝ p )是指存在映身 f: ，且 f滿足： (1)有一個計算 f的多項式時間確定性圖靈機； (2)對于所有 x∈ ， x∈ ， 當(dāng)且僅當(dāng) f(x)∈ 。為了證明 3SAT∈NPC ，只要證明 CNFSAT∝ p 3SAT， 即合取范式的可滿足性問題可在多項式時間內(nèi)變換為 3SAT。 其次，通過證明 3SAT∝ pHAMCYCLE， 得出： HAMCYCLE∈NPC 。 因此， TSP∈NPC 。 36 子集和問題 （ SUBSETSUM） 問題描述： 給定整數(shù)集合 S和一個整數(shù) t， 判定是否存在 S的一個子集 S’?S， 使得 S’中整數(shù)的和為 t。 （ 詳細(xì)證明見書本 P307～ 310） 1x kx1A 2A mA31 一些典型的 NP完全問題 部分 NP完全問題樹 32 合取范式的可滿足性問題 （ CNFSAT） 要證明 CNFSAT∈NPC ， 只要證明在 Cook定理中定義的布爾表達式 A， … ， G或者已是合取范式，或者有的雖然不是合取范式，但可以用布爾代數(shù)中的變換方法將它們化成合取范式，而且合取范式的長度與原表達式的長度只差一個常數(shù)因子。 多項式時間可驗證語言類 VP可定義為： 定理 85： VP=NP。 24 P類與 NP類語言 NP類語言舉例 —— 無向圖的團問題 。 問題的變換與問題的計算復(fù)雜性歸約的關(guān)系 ： 在命題 1和命題 2中，當(dāng) τ(n)=o(T(n)) 時，問題 A的下界歸約為問題 B的下界，問題 B的上界歸約為問題 A的上界。如果某個讀寫頭無限地向右移動而不停機， S(n)也無定義。其中， x=( x1， x2， … ， xn)是輸入， fv是一個代數(shù) 函數(shù)。 缺點： 所需的機器字長要遠(yuǎn)大于其他模型。 (4)常見函數(shù)的計算，如三角函數(shù)，指數(shù)函數(shù)，對數(shù)函數(shù)等。以后除特別注明， RAM程