【正文】 類 ，記為 NPC。這顯然可以在 時(shí)間內(nèi)完成。因此，團(tuán)問題可表示為語言： CLIQUE={wv|w， v∈{0 ， 1}*， 以 w為鄰接矩陣的圖 G有一個(gè) k頂點(diǎn)的團(tuán)，其中 v是 k的二進(jìn)制表示。x 1,x2,… ,xk)中隨意選定一個(gè)值作為它的函數(shù)值。由命題 1即知，元素惟一性問題的計(jì)算時(shí)間下界 也是判別函數(shù)問題的一個(gè)計(jì)算時(shí)間下界。 通過問題變換的技巧，可以將 2個(gè)不同問題的計(jì)算復(fù)雜性聯(lián)系在一起。 )(nT))(( 2 nTO 定理 84 對(duì)于問題 P的任何長(zhǎng)度為 n的輸入，設(shè)求解問題 P的算法 A在 RAM模型下，不含有乘法和除法指令，且按對(duì)數(shù)耗費(fèi)標(biāo)準(zhǔn)其時(shí)間復(fù)雜性為 ，那么，算法 A在 k帶圖靈機(jī)模型 TM下的時(shí)間復(fù)雜性為 。它是從 Q?Tk的某一子集映射到 Q? (T?{L， R，S})k的函數(shù)。 (3)獨(dú)立地將任何一個(gè)或所有讀寫頭，向左移動(dòng)一個(gè)方格 (L)或向右移動(dòng)一個(gè)方格 (R)或停在當(dāng)前單元不動(dòng) (S)。 1vv ff ? 2vf cfv ? 1vf 1vv ff ?1vf 2vf1vf 1vf 1vf1vf13 RAM模型的變形與簡(jiǎn)化 7. 代數(shù)判定樹 ADT(Algebraic Decision Tree) 在代數(shù)計(jì)算樹 T中，若將所有的簡(jiǎn)單結(jié)點(diǎn)都?jí)嚎s到其最近 的子孫分支結(jié)點(diǎn)處，并將簡(jiǎn)單結(jié)點(diǎn)處的計(jì)算在壓縮后的分支結(jié)點(diǎn) 處同時(shí)完成，則計(jì)算結(jié)果可看作是輸入 x的一個(gè)代數(shù)函數(shù) fv(x)。指向該結(jié) 點(diǎn)右兒子的邊相應(yīng)于 xy， 標(biāo)號(hào)為 。 在位式計(jì)算模型下，每個(gè)邏輯運(yùn)算指令耗費(fèi)一個(gè)單位時(shí)間。 由此，對(duì)每一個(gè)固定的 n得到一個(gè)無循環(huán)的直線式程序。下列的各 運(yùn)算為基本運(yùn)算且每個(gè)運(yùn)算只耗費(fèi)單位時(shí)間。每條 RASP指令占據(jù) 2個(gè)連續(xù)的寄存器。在輸入帶的第一個(gè)方 格中放入符號(hào) a1， 第二個(gè)方格中放入符號(hào) a2， … ， 第 n個(gè)方格中 放入符號(hào) an。 將字符串 S=a1a2… an放在輸入帶上。因此若設(shè) l(i)是整 數(shù) i所占的二進(jìn)制位數(shù)，則 ? ?001||lo g)(??????iiiil6 隨機(jī)存取存儲(chǔ)程序機(jī) RASP 1. RASP的結(jié)構(gòu) RASP的整體結(jié)構(gòu)類似于 RAM， 所不同的是 RASP的程序是存儲(chǔ)在寄存器中的。 7 RAM模型的變形與簡(jiǎn)化 1. 實(shí)隨機(jī)存取機(jī) RRAM 在 RRAM模型下，一個(gè)存儲(chǔ)單元可以存放一個(gè)實(shí)數(shù)。在這種情 況下，可以用重復(fù)地寫出相同指令組的方法來消除程序中的循環(huán)。 用 ∧ 代表與， ∨ 代表或， ?代表異或， ?代表非。指向該結(jié)點(diǎn)左兒子的邊相應(yīng)于 x≤y ， 標(biāo)號(hào)為 ≤ 。 (3)每個(gè)有 2個(gè)兒子的內(nèi)部結(jié)點(diǎn) (分支結(jié)點(diǎn) )v， 表示下列形式的 測(cè)試指令： 0或 ≥0 或 =0 其中， 是結(jié)點(diǎn) v在樹 T中的祖先結(jié)點(diǎn) v1處得到的結(jié)果值，或是 x的分量。 (2)清除當(dāng)前讀寫頭下的方格中原有帶符號(hào)并寫上新的帶符號(hào)。 (7)δ 是移動(dòng)函數(shù)。 定理 83 對(duì)于問題 P的任何長(zhǎng)度為 n的輸入，設(shè)求解問題 P的算法 A在 k帶圖靈機(jī)模型 TM下的時(shí)間復(fù)雜性為 ，那么，算法 A在 RAM模型下的時(shí)間復(fù)雜性為 。特別地，當(dāng) τ(n) 為 n的線性函數(shù)時(shí)，稱問題 A可線性地變換為問題 B。任何一個(gè)計(jì)算判別函數(shù)的算法，計(jì)算出判別函數(shù)值后，再作一次測(cè)試，判斷其值是否為 0，即可得到元素惟一性問題的解。可以在δ(q。 若用鄰接矩陣表示圖 G， 用二進(jìn)制串表示整數(shù) k， 則團(tuán)問題的一個(gè)實(shí)例可以用長(zhǎng)度為 的二進(jìn)位串表示。若 V’是一個(gè)團(tuán)則接受輸入，否則拒絕輸入。 如果有一個(gè)語言 L滿足上述性質(zhì) (2)，但不一定滿足性質(zhì) (1)，則稱該語言是 NP難 的。 證明： SAT的一個(gè)實(shí)例是 k個(gè)布爾變量 ， … ， 的 m個(gè)布爾表達(dá)式 ， … ， 若存在各布爾變量 (1≤ i≤k) 的 0， 1賦值，使每個(gè)布爾表達(dá)式 (1≤ i≤m) 都取值 1，則稱布爾表達(dá)式 … 是可滿足的。 這里的因子是變量 或 。 35 頂點(diǎn)覆蓋問題 （ VERTEXCOVER） 證明思路： 首先， VERTEXCOVER∈NP 。因此， SUBSETSUM∈NP ； 其次，證明 VERTEXCOVER∝ pSUBSETSUM。 這個(gè)過程顯然可在多項(xiàng)式時(shí)間內(nèi)完成，即 TSP∈