第四講NP完全性理論

1、NP完全性理論1內(nèi)容計(jì)算的形式描述計(jì)算模型可計(jì)算性理論P(yáng)類與NP類問題NP完全性理論NP完全性的典型例子21 理論計(jì)算模型圖靈機(jī)A.Turing在1936年介紹了這樣一個(gè)通用的計(jì)算模型，該模型具有以下兩個(gè)性質(zhì)該模型的每個(gè)過程都是有窮可描述的；過程必須是由離散的、可以機(jī)械執(zhí)行的步驟組成。圖靈機(jī)是計(jì)算機(jī)的一種簡(jiǎn)單數(shù)字模型，盡管簡(jiǎn)單，但它具有模擬通用計(jì)算機(jī)的計(jì)算能力。為算法和可計(jì)算性研究提供了形式化描述工具。3FinitecontrolX1BB.X2XnXi帶（tape）單元格（cell）帶符（tape symbol） 讀寫頭在每一時(shí)刻掃描帶上的一個(gè)單元 帶有一個(gè)最左單元，向右則是無限的。 帶的每個(gè)

2、單元可容納一個(gè)帶符號(hào)開始時(shí)，最左邊n個(gè)單元裝著輸入（n0，n為有限數(shù)），它是一個(gè)字符串，符號(hào)都選自“帶符號(hào)”的一個(gè)子集，即所謂的“輸入符號(hào)集合”。余下的有窮個(gè)單元都存放空白符，它是一個(gè)特殊的帶符號(hào)，但不是輸入符號(hào)。圖靈機(jī)的基本模型4圖靈機(jī)（Turing Machine)帶子可讀可寫無限長的帶子讀寫頭可左移右移 有限狀態(tài)控制器1111110000000BBB15在一個(gè)圖靈機(jī)的動(dòng)作中，圖靈機(jī)根據(jù)帶頭（讀寫頭）所掃描的符號(hào)和有限控制器的狀態(tài)可能作改變狀態(tài)在被掃描的帶單元上重新寫一個(gè)符號(hào)，以代替原來寫在該單元上的符號(hào).將帶頭向左或者右移一個(gè)單元。 圖靈機(jī)的工作機(jī)制6圖靈機(jī)的形式化描述 有限狀態(tài)集 有限

3、輸入符號(hào)集 有限帶符號(hào)集 轉(zhuǎn)移函數(shù) 開始狀態(tài) 特殊帶符:空白符 終態(tài)集合q0 Q T B T F Q轉(zhuǎn)移函數(shù) : Q Q L,R 形式定義 一個(gè)圖靈機(jī) TM (Turing machine) 是一個(gè)七元組 M = (Q, T, , , q0 , B , F ). 7其他圖靈機(jī)模型“實(shí)際的”的圖靈機(jī)模型單帶圖靈機(jī)（1TM）多帶圖靈機(jī)（kTM）隨機(jī)存取機(jī)（RAM）“實(shí)際的”單位時(shí)間內(nèi)完成的工作量有一個(gè)多項(xiàng)式上界所有“實(shí)際的”計(jì)算模型多項(xiàng)式時(shí)間等價(jià)82 P類與NP類問題算法的時(shí)間復(fù)雜度（分成二類）多項(xiàng)式時(shí)間指數(shù)時(shí)間可計(jì)算與不可計(jì)算9 10 20 30 40 50 60.00001 .00002 .0

4、0003 .00004 .00005 .00006second second second second second second.0001 .0004 .0009 .0016 .0025 .0036second second second second second second .001 .008 .027 .064 .125 .216second second second second second second .1 3.2 24.3 1.7 5.2 13.0second second second minutes minutes minutes .001 1.0 17.9 12.

5、7 35.7 366second second minutes days years centuries .059 58 6.5 3855 2*108 1.3 *1013second minutes years centuries centuries centuriesnn2n3n52n3nSize nTimecomplexityfunction多項(xiàng)式與指數(shù)函數(shù)時(shí)間比較10nn2n3n52n3nN1N2N3N4N5N6100N110N24.64N32.5N4N5 +6.641000N131.6N210N33.98N4N6 +4.19N5 +9.97N6 +6.29Timecomplexityf

6、unctionWith presentcomputerWith computer100 times fasterWith computer1000 times faster1小時(shí)能解決的最大規(guī)模11指數(shù)災(zāi)難：計(jì)算量的指數(shù)增長12Non-deterministic algorithms目前所講的算法都有一個(gè)前提假設(shè)，就是它的每個(gè)運(yùn)算(operation)的結(jié)果都是獨(dú)一(確定)的。這種性質(zhì)的算法可以在實(shí)際的電腦上執(zhí)行，稱為 deterministic algorithms.在討論計(jì)算理論時(shí)，可以將這種限制拿掉，也就是可以假設(shè)一個(gè)運(yùn)算的結(jié)果不唯一，可能是某 n 個(gè)結(jié)果中的一個(gè)，而且一定會(huì)是正確的那一

7、個(gè)。這樣子的算法稱為 non-deterministic algorithm。這種算法無法在實(shí)際的電腦上執(zhí)行。13我們定義下列三個(gè)涵數(shù)來說明這種算法。Choice(S): 從 S 中選一個(gè)正確的答案來(若正確答案存在的話)。Failure(): 沒有成功地完成工作。Success(): 成功地完成工作這三個(gè)涵數(shù)的執(zhí)行時(shí)間都是 O(1)。只有在不可能有正確答案的情形下， non-deterministic algorithm 才無法成功地完成工作。一個(gè)可以執(zhí)行 non-deterministic algorithm 的機(jī)器稱為 non-deterministic machine.14Exampl

8、e 1 searchingA1:n 是一個(gè) n 個(gè)元素的集合，要在 A 中搜尋一個(gè)元素 x 的 non-deterministic algorithm 如下：int j = Choice(1, n);if (Aj = x) cout j; Success();cout 0; Failure();因?yàn)?Choice(1, n) 一定會(huì)找出一個(gè)正確的值，所以拿它找出來的值 j 來比較 Aj = x 若不成立的話，就表示 x 不在 A 裡面。Time complexity 是 O(1)。15Example 2 Sorting要將 A1:n 中的元素作 non-decreasing 的排列，non-d

9、eterministic algorithm 如下 void Nsort(int A, int n) int BSIZE, i, j; for(i=1;i = n;i+) Bi = 0;/初值化 for(i=1;i = n;i+) j = Choice(1, n);/選一個(gè)正確的位置 if(Bj) Failure();/確認(rèn)Bj 沒有被用過 Bj = Ai; for(i = 1;i Bi+1) Failure();/作確認(rèn) for(i=1;i = n;i+) cout Bi ; cout endl; Success(); Time complexityO(n)16要如何來看待 non-dete

10、rministic algorithm 呢？可以用平行處理的角度來看，也就是當(dāng)作同時(shí)有很多很多機(jī)器一起作同一個(gè)問題，每個(gè)機(jī)器用不同的 choice 的結(jié)果來作，若有一個(gè)成功的話，其他的就不用再作；若某個(gè)失敗、就自己停下來即可。另外更好的解釋是，實(shí)際上可能有一種方法可以選擇一個(gè)正確的答案出來(只要正確答案存在)，只是我們還不曉得而已（上帝知道），Choice(S) 就代表可以找到 S 中正確答案的函數(shù)(若正確答案存在)。若正確答案不存在的話，Choice(S) 還是會(huì)找出一個(gè)答案，所以我們需要確認(rèn)此答案是否正確。17Definition Any problem for which the ans

11、wer is either zero or one is called a decision problem. An algorithm for a decision problem is termed a decision algorithm. Any problem that involves the identification of an optimal (either minimum or maximum) value of a given cost function is known as an optimization problem. An optimization algor

12、ithm is used to solve an optimization problem.18非確定型圖靈機(jī)（NTM)猜想階段驗(yàn)證階段 有限狀態(tài)控制器1111110000000BBB1猜想模塊19非確定型圖靈機(jī)的形式化 有限狀態(tài)集 有限輸入符號(hào)集 有限帶符號(hào)集 轉(zhuǎn)移函數(shù) 開始狀態(tài) 特殊帶符:空白符 終態(tài)集合q0 Q T B T F Q轉(zhuǎn)移函數(shù) : 可隨機(jī)選擇 形式定義 一個(gè)非確定型圖靈機(jī) TM 是一個(gè)七元組 M = (Q, T, , , q0 , B , F ). 20P類（Polynomial)P類具有多項(xiàng)式時(shí)間算法的判定問題形成的計(jì)算復(fù)雜性類在確定型圖靈機(jī)上多項(xiàng)式時(shí)間可解的問題21NP類

13、(Nondeterministic Polynomial )NP問題：在非確定型圖靈機(jī)上多項(xiàng)式時(shí)間可解的問題在確定型圖靈機(jī)上多項(xiàng)式時(shí)間可驗(yàn)證的問題P類包含于NP類中NP類問題在確定圖靈機(jī)上指數(shù)時(shí)間可解非確定型圖靈機(jī)和確定型圖靈機(jī)的計(jì)算能力相當(dāng)22Commonly believed relationship between P and NP一般相信 P 與 NP 兩集合不相同，也就是相信有些問題是屬於 NP 而不屬於 P，但目前仍然無法證明。Cook 曾問過一個(gè)問題：有沒有什麼問題應(yīng)該屬於 NP 而不屬於 P，如果該問題屬於 P 的話，就表示 P = NP 呢？PNP23Satisfiabili

14、ty ProblemGiven a Boolean formula (with variables and Boolean operators AND, OR and NOT), is it satisfiable?Is there an assignment of values 0 or 1 to variables so that the formula evaluates to 1?Conjunctive Normal Form (CNF)A clause is the OR of some literalsA Boolean formula consisting of several

15、clauses separated by AND is a CNF formulaE.g., (a+b+c)(b+d+e+f)(a+e)24Satisfiability Problem contd3-CNF: a CNF formula in which each clause has 3 literalsE.g., (a+b+c)(d+e+f)(a+f+g)Given a 3-CNF formula, is it satisfiable?That is, is there an assignment (to variables) that evaluates the formula to 1

16、This is also called the 3-CNF-SAT problem25Non-deterministic satisfiability void Eval(cnf E, int n) int xSIZE; for(int i=1;i = n;i+) xi = Choice(0, 1); if(E(x, n) Success(); else Failure; 這個(gè)演算法的 time complexity 是 O(n) 再加上 E(x, n) 的時(shí)間，計(jì)算 propositional formula 值的時(shí)間與該 formula 的長度有關(guān)。這是第一個(gè)被證明為 NP-complet

17、e 的問題。26Cook 自己提出一個(gè)答案，就是下面的定理。Theorem cookSatisfiability is in P if and only if P = NP. satisfiability 是第一個(gè) NP-complete 的問題。要定義 NP-hard 與 NP-complete 之前，我們需要再定義一個(gè)名詞： reducibility.27Let L1 and L2 be problems. L1 reduces to L2(also written ) if and only if there is a way to solve L1 by a deterministic

18、 polynomial time algorithm using a deterministic algorithm that solves L2 in polynomial time.只要 L2 有 polynomial time 演算法，則 L1 也存在 polynomial time 演算法。例如 L1 是從 n 個(gè)數(shù)字中找出最大的數(shù)字，而 L2 是將 n 個(gè)數(shù)字中第 k 大的數(shù)字找出來，而 L3 是將 n 個(gè)數(shù)字作排序，則 L1 L2 L3。 28Definition A problem L is NP-hard if and only if satisfiability reduce

19、s to L (satisfiability ). A problem L is NP-complete if and only if L is NP-hard and NP.PNPNP-hardNP-complete29同一個(gè)問題的 decision 版本與 optimization 版本常常可以互相 reduce，像 max clique其實(shí) reducibility 還有更多種定義。Halting problem 是一個(gè) NP-hard 的問題，因?yàn)?satisfiability 的問題可以 reduce 成 halting problem。Halting problem 的問題是輸入一

20、個(gè)演算法 A 與此 A 的 input I，決定 A 輸入 I 時(shí)會(huì)不會(huì)停(或者進(jìn)入無窮迴圈)。這個(gè)問題是 undecidable(無法決定的)，也就是不存在任何(時(shí)間複雜度的)演算法來解決這個(gè)問題，所以這個(gè)問題不屬於 NP。30接下來證明 satisfiability halting problem，寫一個(gè)演算法 A，A 的 input 是 propositional formula X，若 X 中有 n 個(gè)變數(shù)，則測(cè)試 2n 種組合，若其中有一種使 X 為 true 的話，A 就停止；否則 A 就進(jìn)入無窮迴圈。以這個(gè) A 與 X 當(dāng)作 halting problem 的輸入，如果 halt

21、ing problem 的回答是會(huì)停，則 satisfiability 的答案就是 yes，若 halting problem 的回答是不會(huì)停，則 satisfiability 就是 no。因此 halting problem 若有 polynomial time 演算法的話、satisfiability 同樣有polynomial time 演算法。故得證。31Definition Two problems L1 and L2 are said to be polynomially equivalent iff and .要證明一個(gè)問題 L2 是 NP-hard 的話，較簡(jiǎn)單的作法是找一個(gè)已

22、知的 NP-hard 問題 L1，證明。因?yàn)閞educible 是有遞移性的，所以 satisfiability 要證明一個(gè)NP-hard decision problem 是 NP-complete, 只要找出它的polynomial time non-deterministic algorithm 即可32NP完全問題第一個(gè)NP完全問題（Cook定理 1971）可滿足性問題是NP完全問題六個(gè)NP完全問題（Karp 1972)3SAT，3DM，VC，團(tuán)，HC，劃分更多的NP完全問題1979年：300多個(gè)1998年：2000多個(gè)33一些典型的NP完全問題團(tuán)問題Subset Sum Satisf

23、iabilityHamiltonian CycleTraveling Salesperson34Example Maximum cliqueA maximal complete sub-graph of a graph G = (V, E) is a clique. 其 clique 的大小就看此 clique 的點(diǎn)數(shù)。max clique problem 是一個(gè) optimization problem，找出一個(gè)圖形最大的 clique。這個(gè)問題也可以有 decision的版本，就是 G 的 clique 之大小會(huì)不會(huì)比數(shù)字 k 還大。(輸入：G 與 k)如果 optimization pr

24、oblem 可以 g(n) 的時(shí)間內(nèi)作出來，則 decision 版本也可以在 g(n) 時(shí)間內(nèi)作好。如果 decision 版本可以 f(n) 時(shí)間內(nèi)完成，則 optimization 版本可以在 n f(n) (?)的時(shí)間內(nèi)完成。所以兩者一定同時(shí)為 polynomial time 或同時(shí)不為 polynomial time。35Example Max clique void DCK(int GSIZE, int n, int k) S = ; for(int i=1;i = k;i+) int t = Choice(1, n); if(t is in S) Failure(); S = S

25、 t; for(all pairs(i, j) such that i is in S, j is in S and i != j) if(i, j) is not an edge of G) Failure(); Success(); Non-deterministic clique pseudocode36Satisfiability令 x1, x2, 代表 boolean variables，而 代表 xi 的相反。A formula 是這些布林變數(shù)與 logic AND、logic OR 的組合。Conjunctive normal form(CNF)Disjunctive norma

26、l form(DNF)The satisfiability problem is to determine whether a formula is true for some assignment of truth values to the variables.CNF-satisfiability37Non-deterministic satisfiability void Eval(cnf E, int n) int xSIZE; for(int i=1;i = n;i+) xi = Choice(0, 1); if(E(x, n) Success(); else Failure; 這個(gè)

27、演算法的 time complexity 是 O(n) 再加上 E(x, n) 的時(shí)間，計(jì)算 propositional formula 值的時(shí)間與該 formula 的長度有關(guān)。這是第一個(gè)被證明為 NP-complete 的問題。38Graph Coloring ProblemGiven a graph, how to color vertices so that adjacent ones have different colorsChromatic number is the smallest number of colors needed to color a graphThe graph coloring problemOptimization problem: Given a graph G=(V,E), find the chromatic numberDecision problem: Given a graph G=(V,E) and an integer k, is G k-colorable?39Subset Sum ProblemGiven a set S of positive integers and an integer k Is there a subset R of S such that