![](//blog.wenxuecity.com/images/pixel_trans.gif) |
PNPNPC問題 1。基本概念:問題複雜度和算法複雜度;具體問題和抽象問題;判定性問題; 2。編碼對問題解決效率的影響(效率與編碼方式的依賴性相當嚴重),多項式相關編碼,多項式時間可計算函數; 3。複雜類P A polynomially bounded algorithm is one with its worst-case complexity bounded by a polynonial function of the input size. A polynonially bounded problem is one for which there is a polynomially bounded algorithm. The class P is the class of decision problems that are polynomially bounded 定義一:多項式時間內可解決的具體判定性問題的集合; 定理一:設Q是定義在實例集I上的一個抽象判定問題,e1,e2是I上的多項式相關編碼,則e1(Q)∈P ←→ e2(Q)∈P 定義二:P = {L包含於{0,1}* | 存在一個算法A可在多項式時間內判定L } 定理二:P = {L包含於{0,1}* | 存在一個算法A可在多項式時間內接受L },定理二的證明采用模擬論證; 定義三:P是確定型單帶圖靈機在多項式時間內可判定的語言類: P=∪TIME(n^k), k = 0,1,2... 其中時間複雜類TIME(t(n))定義為 TIME(t(n))={L | L是一個由O(t(n))時間的圖靈機判定的語言} 4。多項式時間驗證: 有一個算法A所驗證的語言是: L={x∈{0,1}* | 存在y∈{0,1}*滿足A(x,y)=1} 5。複雜類NP: 定義一:一個語言L屬於NP當且僅當存在一個兩輸入的多項式時間算法A和常數c滿足: L={x∈{0,1}* | 存在一個證書y, |y|=O(|x|^c), 滿足A(x,y)=1 } 即算法A在多項式時間內驗證了語言L。 定義二:一個語言在NP中,當且僅當它能被某個非確定型多項式時間圖靈機判定,即 NP=∪NTIME(n^k), k = 0,1,2... 其中時間複雜類NTIME(t(n))定義為 NTIME(t(n))={L | L是一個被O(t(n))時間的非確定型圖靈機判定的語言} A polynomial bounded nondeterministic algorithm is one for which there is a (fixed) polynomial function p such that for each input of size n for which the answer is yes , there is some execution of the algorithm that produces a yes output in at most p(n) steps. The class NP is the class of decision problems for which there is a polynonial bounded nondeterministic algorithm. 解釋說明:nondeterministic algorithm就是定義一中的那個驗證算法A, nondeterministic algorithm會用某種非確定性的算法生成一個證書並對其進行驗證,然後輸出結果; 上述的英文定義實際上是從非確定性多項式時間圖靈機的角度來定義NP類,即和定義二等價; 注意: L∈P → L∈NP, 因此P包含於NP;目前還不知道P是否等於NP 證明一個問題L屬於NP,隻要證明對於L的一個輸入實例x和該實例的一個證書y(y的編碼長度是輸入x的編碼長度的多項式),存在一個多項式時間的算法A可以驗證y是否滿足x 6。P在交並補和Kleene*運算下封閉(證明);NP在交並補和Kleene*運算下是否封閉還未知; 7。多項式時間化簡: 如果存在一個多項式時間的可計算函數f:{0,1}* → {0,1}*,滿足對於所有的x∈{0,1}*, x∈L1 ←→ f(x)∈L2, 則稱L1在多項式時間內可化簡為L2,記作L1 <=p L2 Polynomial Reduction Let T be a function from the input set for a dicision problem P into the input set for Q. T is a polynomial reduction from P to Q if: T can be computed in polynomial bounded time x is a yes input for P → T(x) is a yes input for Q x is a no input for P → T(x) is a no input for Q polynomially reducible Problem P is polynomially reducible to Q if there exists a polynomial reduction from P to Q, denoted as: P <=p Q 8。定理:如果L1,L2包含於{0,1}*,滿足L1 <=p L2,則L2∈P → L1∈P 該定理用構造法易證;這個定理可用於證明某個問題是否為NP; If P <=p Q and Q is in P, then P is in P The complexity of P is the sum of T, with the input size n, and Q, with the input size p(n), where p is the polynomial bound on T, So, the total cost is: p(n)+q(p(n)), where q is the polynomial bound on Q. (If P <=p Q, then Q is at least as “hard” to solve as P) 和這個定理相關的一個引理: 對多項式時間的子程序間進行至多常數次調用的算法的運行時間還是多項式時間; 但是對多項式時間的子程序間進行多項式次調用可能產生一個指數時間的算法; 該引理表明了多項式時間化簡(Polynomial Reduction)的傳遞性(transitivity) 9。複雜類NPC: 定義一:如果語言L滿足 1. L∈NP; 2. 對每一個L'∈NP,有 L' <=p L,即L是NP-hard的; 則稱L∈NPC A problem Q is NP-hard if every problem P in NP is reducible to Q, that is P <=p Q. (which means that Q is at least as hard as any problem in NP ) A problem Q is NP-complete if it is in NP and is NP-hard. (which means that Q is at most as hard as to be solved by a polynomially bounded nondeterministic algorithm) 注意:一個Np-hard的問題不一定屬於Np,譬如某問題L滿足每一個L'∈NP,有 L' <=p L; 但是該問題L不能在多項式時間內被驗證,則L是NP-hard的但是不屬於NP; 隻有當L是NP-hard且L∈NP,才有L∈NPC; 定理一:NPC=P ←→ NP=P 定理二:B∈NPC且B <=p C 則C∈NPC; 定理二是用Polynomial Reductions證明一個問題是NPC的依據; 10。SAT問題: 判斷一個布爾公式是否可滿足(即是否存在一組賦值使該布爾公式結果為true)。 SAT = {<φ> | φ是可滿足的布爾公式} Cook’s theorem: The satisfiability problem is NP-complete Reduction as tool for proving NP-complete Since CNF-SAT is known to be NP-hard, then all the problems, to which CNF-SAT is reducible, are also NP-hard. So, the formidable task of proving NP-complete is transformed into relatively easy task of proving of being in NP. Cook's theorem的證明見《Introduction to the Theroy of Computation》Chapter 8.4.3 11。3SAT問題: “文字”是指一個布爾變量或布爾變量的非 “子句”是由∨連接起來的若幹文字; 一個布爾公式,若是由∧連接的若幹子句組成,則稱為合取範式(cnf) 若所有的子句都由三個文字,則稱為3cnf公式 3SAT={<φ> | φ是可滿足的3cnf公式} 定理:3SAT∈NPC 證明方法和SAT的證明類似;也可以利用邏輯公式的語法樹在多項式時間內構造一個等價的3cnf公式來證明; 證明一個問題Q屬於NPC的常用方法是證明3SAT問題可多項式化簡到Q; 12。證明一個問題Q是NPC的過程: Prove problem Q is NP-complete, given a problem P known to be NP -complete For all R∈NP, R <=p P; Show P <=p Q; // this is the KEY step By transitivity of reduction, for all R∈NP, R <=p Q; So, Q is NP-hard; If Q is in NP as well, then Q is NP-complete. 13。幾種常見的多項式化簡 (1) SAT <=p 3SAT 構造原始公式φ的語法樹,引入中間變量yi作為每個內部節點的輸出,然後把原始公式φ改寫為根變量與描述每個頂點操作的子句的合取的“與”公式,這樣經改寫後的表達式為各個項的合取式,且每一項都有3個文字;然後將每一項變為由∨連接的子句,這可以通過窮舉每一項的三個文字的真值表做到(邏輯電路中的方法) (2) 3SAT <=p CLIQUE (EX13.18) 設φ是有k個子句的3cnf公式,歸約f輸出結果為,其中G是如下定義的無向圖: 中的每個節點分為k組,每組3個節點,稱為三元組t1,t2,..tk;每個三元組對應於φ中的一個子句,三元組中的每個節點對應於相關子句的一個文字;如果以下兩個條件同時滿足,我們就用一條邊連接兩個頂點u 和v: 1.u和v處於不同的三元組中; 2.他們的相應文字是一致的,即u所代表的文字不是v所代表的文字的非; 這樣很容易證明3SAT <=p CLIQUE (3) CLIQUE <=p VERTEX-COVER (EX13.20) 利用補圖來進行化簡。對於一個無向圖G=(V,E),定義G的補圖G'=(V,E'),其中E'={(u,v)|(u,v)不屬於E}。 化簡算法的輸入是CLIQUE的實例,它計算出G的補圖G',這很容易在多項式時間內完成;化簡算法的輸出是VERTEX-COVER的實例。易證G具有一個規模為k的Clique當且僅當G'具有一個規模為|V|-k的Vertex-Cover; (4) VERTEX-COVER <=p SUBSET-SUM 化簡算法的核心在於圖G的關聯矩陣表示。 設G=(V,E)是一個無向圖,G的關聯矩陣是一個|V|*|E|的矩陣B,其中B[i,j]=1當且僅當頂點vi與邊ej向關聯,否則B[i,j]=0; 然後采用基數為4的方法表示數,具體過程比較複雜~~ :( (5) SUBSET-SUM <=p JOB-SCHEDULING 設SUBSET-SUM實例為<{si},C>,並設S=∑si 構造一個JOB-SCHEDULING實例<{ti}, {di}, {pi}, k> 為 : if S-C < 0 , ti=2, di=pi=1, k=0 otherwise, ti=pi=si, di=C, for 1<=i<=n, and k-S-C 下麵的過程顯而易見; (6) 3SAT <=p HAM-CYCLE 核心是幾個特殊構造的“附件圖”,具體過程比較複雜~~ (7) HAM-CYCLE <=p TSP (EX13.11) 設G=(V,E)是HAM-CYCLE的一個實例,構造TSP實例如下: 建立一個完全圖G'=(V,E'),其中E'={(i,j) | i,j∈V },定義費用函數c為: c(i,j) = 0 , if (i,j) ∈ E; c(i,j) = 1 , otherwise 於是 就是TSP的實例; 易證G中具有哈密爾頓回路當且僅當G'中存在一條費用至多為0的TSP回路。 (注:EX13.12的證明: 隻要修改上述費用函數為c(i,j)=1, if (i,j)∈ E, otherwise c(i,j)=2, 得到的TSP實例為, 這樣即使當TSP的費用函數限製在{1,2}上他還是屬於NPC的 ) (8) HAM-CYCLE <=p UHAM-CYCLE |
![](//blog.wenxuecity.com/images/pixel_trans.gif) |
|