第四讲NP完全性理论

1、NP完全性理论1内容计算的形式描述计算模型可计算性理论P类与NP类问题NP完全性理论NP完全性的典型例子21 理论计算模型图灵机A.Turing在1936年介绍了这样一个通用的计算模型，该模型具有以下两个性质该模型的每个过程都是有穷可描述的；过程必须是由离散的、可以机械执行的步骤组成。图灵机是计算机的一种简单数字模型，尽管简单，但它具有模拟通用计算机的计算能力。为算法和可计算性研究提供了形式化描述工具。3FinitecontrolX1BB.X2XnXi带（tape）单元格（cell）带符（tape symbol） 读写头在每一时刻扫描带上的一个单元 带有一个最左单元，向右则是无限的。 带的每个

2、单元可容纳一个带符号开始时，最左边n个单元装着输入（n0，n为有限数），它是一个字符串，符号都选自“带符号”的一个子集，即所谓的“输入符号集合”。余下的有穷个单元都存放空白符，它是一个特殊的带符号，但不是输入符号。图灵机的基本模型4图灵机（Turing Machine)带子可读可写无限长的带子读写头可左移右移 有限状态控制器1111110000000BBB15在一个图灵机的动作中，图灵机根据带头（读写头）所扫描的符号和有限控制器的状态可能作改变状态在被扫描的带单元上重新写一个符号，以代替原来写在该单元上的符号.将带头向左或者右移一个单元。 图灵机的工作机制6图灵机的形式化描述 有限状态集 有限

3、输入符号集 有限带符号集 转移函数 开始状态 特殊带符:空白符 终态集合q0 Q T B T F Q转移函数 : Q Q L,R 形式定义 一个图灵机 TM (Turing machine) 是一个七元组 M = (Q, T, , , q0 , B , F ). 7其他图灵机模型“实际的”的图灵机模型单带图灵机（1TM）多带图灵机（kTM）随机存取机（RAM）“实际的”单位时间内完成的工作量有一个多项式上界所有“实际的”计算模型多项式时间等价82 P类与NP类问题算法的时间复杂度（分成二类）多项式时间指数时间可计算与不可计算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多项式与指数函数时间比较10nn2n3n52n3nN1N2N3N4N5N6100N110N24.64N32.5N4N5 +6.641000N131.6N210N33.98N4N6 +4.19N5 +9.97N6 +6.29Timecomplexityf

6、unctionWith presentcomputerWith computer100 times fasterWith computer1000 times faster1小时能解决的最大规模11指数灾难：计算量的指数增长12Non-deterministic algorithms目前所講的算法都有一個前提假設，就是它的每個運算(operation)的結果都是獨一(確定)的。這種性質的算法可以在實際的電腦上執行，稱為 deterministic algorithms.在討論計算理論時，可以將這種限制拿掉，也就是可以假設一個運算的結果不唯一，可能是某 n 個結果中的一個，而且一定會是正確的那一

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

8、e 1 searchingA1:n 是一個 n 個元素的集合，要在 A 中搜尋一個元素 x 的 non-deterministic algorithm 如下：int j = Choice(1, n);if (Aj = x) cout j; Success();cout 0; Failure();因為 Choice(1, n) 一定會找出一個正確的值，所以拿它找出來的值 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);/選一個正確的位置 if(Bj) Failure();/確認Bj 沒有被用過 Bj = Ai; for(i = 1;i Bi+1) Failure();/作確認 for(i=1;i = n;i+) cout Bi ; cout endl; Success(); Time complexityO(n)16要如何來看待 non-dete

10、rministic algorithm 呢？可以用平行處理的角度來看，也就是當作同時有很多很多機器一起作同一個問題，每個機器用不同的 choice 的結果來作，若有一個成功的話，其他的就不用再作；若某個失敗、就自己停下來即可。另外更好的解釋是，實際上可能有一種方法可以選擇一個正確的答案出來(只要正確答案存在)，只是我們還不曉得而已（上帝知道），Choice(S) 就代表可以找到 S 中正確答案的函數(若正確答案存在)。若正確答案不存在的話，Choice(S) 還是會找出一個答案，所以我們需要確認此答案是否正確。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非确定型图灵机（NTM)猜想阶段验证阶段 有限状态控制器1111110000000BBB1猜想模块19非确定型图灵机的形式化 有限状态集 有限输入符号集 有限带符号集 转移函数 开始状态 特殊带符:空白符 终态集合q0 Q T B T F Q转移函数 : 可随机选择 形式定义 一个非确定型图灵机 TM 是一个七元组 M = (Q, T, , , q0 , B , F ). 20P类（Polynomial)P类具有多项式时间算法的判定问题形成的计算复杂性类在确定型图灵机上多项式时间可解的问题21NP类

13、(Nondeterministic Polynomial )NP问题：在非确定型图灵机上多项式时间可解的问题在确定型图灵机上多项式时间可验证的问题P类包含于NP类中NP类问题在确定图灵机上指数时间可解非确定型图灵机和确定型图灵机的计算能力相当22Commonly believed relationship between P and NP一般相信 P 與 NP 兩集合不相同，也就是相信有些問題是屬於 NP 而不屬於 P，但目前仍然無法證明。Cook 曾問過一個問題：有沒有什麼問題應該屬於 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; 這個演算法的 time complexity 是 O(n) 再加上 E(x, n) 的時間，計算 propositional formula 值的時間與該 formula 的長度有關。這是第一個被證明為 NP-complet

17、e 的問題。26Cook 自己提出一個答案，就是下面的定理。Theorem cookSatisfiability is in P if and only if P = NP. satisfiability 是第一個 NP-complete 的問題。要定義 NP-hard 與 NP-complete 之前，我們需要再定義一個名詞： 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 個數字中找出最大的數字，而 L2 是將 n 個數字中第 k 大的數字找出來，而 L3 是將 n 個數字作排序，則 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同一個問題的 decision 版本與 optimization 版本常常可以互相 reduce，像 max clique其實 reducibility 還有更多種定義。Halting problem 是一個 NP-hard 的問題，因為 satisfiability 的問題可以 reduce 成 halting problem。Halting problem 的問題是輸入一

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

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

22、知的 NP-hard 問題 L1，證明。因為reducible 是有遞移性的，所以 satisfiability 要證明一個NP-hard decision problem 是 NP-complete, 只要找出它的polynomial time non-deterministic algorithm 即可32NP完全问题第一个NP完全问题（Cook定理 1971）可满足性问题是NP完全问题六个NP完全问题（Karp 1972)3SAT，3DM，VC，团，HC，划分更多的NP完全问题1979年：300多个1998年：2000多个33一些典型的NP完全问题团问题Subset Sum Satisf

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

24、oblem 可以 g(n) 的時間內作出來，則 decision 版本也可以在 g(n) 時間內作好。如果 decision 版本可以 f(n) 時間內完成，則 optimization 版本可以在 n f(n) (?)的時間內完成。所以兩者一定同時為 polynomial time 或同時不為 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 是這些布林變數與 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; 這個

27、演算法的 time complexity 是 O(n) 再加上 E(x, n) 的時間，計算 propositional formula 值的時間與該 formula 的長度有關。這是第一個被證明為 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