第四讲NP完全性理论

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,NP,完全性理论,内容,计算的形式描述计算模型,可计算性理论,P,类与,NP,类问题,NP,完全性理论,NP,完全性的典型例子,1,理论计算模型图灵机,A.Turing,在,1936,年介绍了这样一个通用的计算模型，该模型具有以下两个性质,该模型的每个过程都是有穷可描述的；,过程必须是由离散的、可以机械执行的步骤组成。,图灵机是计算机的一种简单数字模型，尽管简单，但它具有模拟通用计算机的计算能力。为算法和可计算性研究提供了形式化描述工具。,Finite,control,X,1,B,B,.,X,2,X,n,X,i,带（,tape,）,单元格（,cell,）,带符（,tape symbol,）,读写头在每一时刻扫描带上的一个单元,带有一个最左单元，向右则是无限的。,带的每个单元可容纳一个带符号,开始时，最左边,n,个单元装着输入（,n,0,，,n,为有限数），它是一个字符串，符号都选自,“,带符号,”,的一个子集，即所谓的,“,输入符号集合,”,。余下的有穷个单元都存放空白符，它是一个特殊的带符号，但,不是,输入符号。,图灵机的基本模型,图灵机（,Turing Machine),带子可读可写,无限长的带子,读写头可左移右移,有限状态控制器,1,1,1,1,1,1,0,0,0,0,0,0,0,B,B,B,1,在一个图灵机的动作中，图灵机根据带头（读写头）所扫描的符号和有限控制器的状态可能作,改变状态,在被扫描的带单元上重新写一个符号，以代替原来写在该单元上的符号,.,将带头向左或者右移一个单元。,。,图灵机的工作机制,图灵机的形式化描述,有限状态集,有限输入符号集,有限带符号集,转移函数,开始状态,特殊带符,:,空白符,终态集合,q,0,Q,T ,B, T,F,Q,转移函数,: Q,Q,L,R,形式定义,一个图灵机,TM (Turing machine,),是一个七元组,M,= (,Q,T, q,0, B, F,),.,其他图灵机模型,“,实际的”的图灵机模型,单带图灵机（,1TM,）,多带图灵机（,kTM,）,随机存取机（,RAM,）,“,实际的”,单位时间内完成的工作量有一个多项式上界,所有“实际的”计算模型多项式时间等价,2 P,类与,NP,类问题,算法的时间复杂度（分成二类）,多项式时间,指数时间,可计算与不可计算,10 20 30 40 50 60,.00001 .00002 .00003 .00004 .00005 .00006,second second second second second second,.0001 .0004 .0009 .0016 .0025 .0036,second second second second second second,.001 .008 .027 .064 .125 .216,second second second second second second,.1 3.2 24.3 1.7 5.2 13.0,second second second minutes minutes minutes,.001 1.0 17.9 12.7 35.7 366,second second minutes days years centuries,.059 58 6.5 3855 2*10,8,1.3 *10,13,second minutes years centuries centuries centuries,n,n,2,n,3,n,5,2,n,3,n,Size n,Time,complexity,function,多项式与指数函数时间比较,n,n,2,n,3,n,5,2,n,3,n,N,1,N,2,N,3,N,4,N,5,N,6,100N,1,10N,2,4.64N,3,2.5N,4,N,5,+6.64,1000N,1,31.6N,2,10N,3,3.98N,4,N,6,+4.19,N,5,+,9.97,N,6,+,6.29,Time,complexity,function,With present,computer,With computer,100 times faster,With computer,1000 times faster,1,小时能解决的最大规模,指数灾难：计算量的指数增长,Non-deterministic algorithms,目前所講的算法都有一個前提假設，就是它的每個運算(,operation),的結果都是獨一(確定)的。這種性質的算法可以在實際的電腦上執行，稱為,deterministic algorithms.,在討論計算理論時，可以將這種限制拿掉，也就是可以假設一個運算的結果不唯一，可能是某,n,個結果中的一個，而且,一定會是正確的那一個,。這樣子的算法稱為,non-deterministic algorithm。,這種算法無法在實際的電腦上執行。,我們定義下列三個涵數來說明這種算法。,Choice(S):,從,S,中選一個正確的答案來(若正確答案存在的話)。,Failure():,沒有成功地完成工作。,Success():,成功地完成工作,這三個涵數的執行時間都是,O(1)。,只有在不可能有正確答案的情形下，,non-deterministic algorithm,才無法成功地完成工作。,一個可以執行,non-deterministic algorithm,的機器稱為,non-deterministic machine.,Example,1,searching,A1: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)。,Example 2 Sorting,要將,A1:n,中的元素作,non-decreasing,的排列，,non-deterministic 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 complexity,O(n),要如何來看待,non-deterministic algorithm,呢？,可以用平行處理的角度來看，也就是當作同時有很多很多機器一起作同一個問題，每個機器用不同的,choice,的結果來作，若有一個成功的話，其他的就不用再作；若某個失敗、就自己停下來即可。,另外更好的解釋是，實際上可能有一種方法可以選擇一個正確的答案出來(只要正確答案存在)，只是我們還不曉得而已（上帝知道），,Choice(S),就代表可以找到,S,中正確答案的函數(若正確答案存在)。若正確答案不存在的話，,Choice(S),還是會找出一個答案，所以我們需要確認此答案是否正確。,Definition,Any problem for which the answer 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,algorithm,is used to solve an optimization problem.,非确定型图灵机（,NTM),猜想阶段,验证阶段,有限状态控制器,1,1,1,1,1,1,0,0,0,0,0,0,0,B,B,B,1,猜想模块,非确定型图灵机的形式化,有限状态集,有限输入符号集,有限带符号集,转移函数,开始状态,特殊带符,:,空白符,终态集合,q,0,Q,T ,B, T,F,Q,转移函数,:,可随机选择,形式定义,一个非确定型图灵机,TM,是一个七元组,M,= (,Q,T, q,0, B, F,),.,P,类（,Polynomial),P,类,具有多项式时间算法的判定问题形成的计算复杂性类,在确定型图灵机上多项式时间可解的问题,NP类,(Nondeterministic Polynomial ),NP,问题：,在非确定型图灵机上多项式时间可解的问题,在确定型图灵机上多项式时间可验证的问题,P,类包含于,NP,类中,NP,类问题在确定图灵机上指数时间可解,非确定型图灵机和确定型图灵机的计算能力相当,Commonly believed relationship between P and NP,一般相信,P,與,NP,兩集合不相同，也就是相信有些問題是屬於,NP,而不屬於,P,，,但目前仍然無法證明。,Cook,曾問過一個問題：有沒有什麼問題應該屬於,NP,而不屬於,P,，,如果該問題屬於,P,的話，就表示,P,=,NP,呢？,P,NP,Satisfiability,Problem,Given 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,literals,A Boolean formula consisting of several clauses separated by AND is a CNF formula,E.g., (,a+b+c)(b+d+e+f)(a+e,),Satisfiability,Problem,contd,3-CNF: a CNF formula in which each clause has 3 literals,E.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,This is also called the 3-CNF-SAT problem,Non-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,-complete,的問題。,Cook,自己提出一個答案，就是下面的定理。,Theorem cook,Satisfiability,is in,P,if and only if,P,=,NP,.,satisfiability,是第一個,NP,-complete,的問題。,要定義,NP,-hard,與,NP,-complete,之前，我們需要再定義一個名詞：,reducibility,.,Let L,1,and L,2,be problems. L,1,reduces to L,2,(also written ) if and only if there is a way to solve L,1,by a deterministic polynomial time algorithm using a deterministic algorithm that solves L,2,in polynomial time.,只要,L,2,有,polynomial time,演算法，則,L,1,也存在,polynomial time,演算法。,例如,L,1,是從,n,個數字中找出最大的數字，而,L,2,是將,n,個數字中第,k,大的數字找出來，而,L,3,是將,n,個數字作排序，則,L,1, L,2, L,3,。,Definition,A problem L is,NP,-hard if and only if,satisfiability,reduces to L (,satisfiability,). A problem L is,NP,-complete if and only if L is,NP,-hard and,NP,.,P,NP,NP,-hard,NP,-complete,同一個問題的,decision,版本與,optimization,版本常常可以互相,reduce，,像,max clique,其實,reducibility,還有更多種定義。,Halting problem,是一個,NP,-hard,的問題，因為,satisfiability,的問題可以,reduce,成,halting problem。,Halting problem,的問題是輸入一個演算法,A,與此,A,的,input I，,決定,A,輸入,I,時會不會停(或者進入無窮迴圈)。這個問題是,undecidable,(,無法決定的)，也就是不存在任何(時間複雜度的)演算法來解決這個問題，所以這個問題不屬於,NP,。,接下來證明,satisfiability,halting problem，,寫一個演算法,A，A,的,input,是,propositional formula X，,若,X,中有,n,個變數，則測試 2,n,種組合，若其中有一種使,X,為,true,的話，,A,就停止；否則,A,就進入無窮迴圈。,以這個,A,與,X,當作,halting problem,的輸入，如果,halting problem,的回答是會停，則,satisfiability,的答案就是,yes，,若,halting problem,的回答是不會停，則,satisfiability,就是,no。,因此,halting problem,若有,polynomial time,演算法的話、,satisfiability,同樣有,polynomial time,演算法。故得證。,Definition,Two problems L,1,and L,2,are said to be,polynomially,equivalent,iff,and .,要證明一個問題,L,2,是,NP,-hard,的話，較簡單的作法是找一個已知的,NP,-hard,問題,L,1,，,證明。因為,reducible,是有遞移性的，所以,satisfiability,要證明一個,NP,-hard decision problem,是,NP,-complete,只要找出它的,polynomial time non-deterministic algorithm,即可,NP,完全问题,第一个,NP,完全问题（,Cook,定理,1971,）,可满足性问题是,NP,完全问题,六个,NP,完全问题（,Karp 1972),3SAT,，,3DM,，,VC,，,团，,HC,，,划分,更多的,NP,完全问题,1979,年：,300,多个,1998,年：,2000,多个,一些典型的,NP,完全问题,团问题,Subset Sum,Satisfiability,Hamiltonian Cycle,Traveling Salesperson,Example Maximum clique,A,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 problem,可以,g(n),的時間內作出來，則,decision,版本也可以在,g(n),時間內作好。,如果,decision,版本可以,f(n),時間內完成，則,optimization,版本可以在,n f(n) (,?,),的時間內完成。所以兩者一定同時為,polynomial time,或同時不為,polynomial time。,Example 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 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,pseudocode,Satisfiability,令,x,1, x,2,代表,boolean,variables，,而 代表,x,i,的相反。,A formula,是這些布林變數與,logic AND、logic OR,的組合。,Conjunctive normal form(CNF),Disjunctive normal form(DNF),The,satisfiability,problem is to determine whether a formula is true for some assignment of truth values to the variables.,CNF-,satisfiability,Non-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,-complete,的問題。,Graph Coloring Problem,Given a graph, how to color vertices so that adjacent ones have different colors,Chromatic number is the smallest number of colors needed to color a graph,The graph coloring problem,Optimization problem,: Given a graph G=(V,E), find the chromatic number,Decision problem,:,Given a graph G=(V,E) and an integer k, is G k-colorable?,Subset Sum Problem,Given a set,S,of positive integers and an integer,k,Is there a subset R of S such that the sum of the elements in R is equal to k?,Example,S,=1,16,64,256,1040,1041,1093,1284,1344 and,k,=3754,R,=1,16,64,256,1040,1093,1284 is a solution,Hamiltonian Path Problem,A Hamiltonian path of a graph,A simple path that passes through every vertex exactly once,Does a given undirected graph has a Hamiltonian path?,Can also specify for directed graphs,Traveling Salesperson Problem,Known as TSP or minimum tour problem,A salesperson wants to minimize total traveling cost (distance or time) required to visit a set of cities and return to the starting point,Given a weighted, complete graph and an integer k, is there a Hamiltonian cycle with total weight at most k?,如何处理,NP,完全问题,实际的问题不会消失,并行计算,以硬件设备换取时间,存在着很多种并行计算模型,理想模型,PRAM,可多项式时间解,NP,完全问题,实际中效果不好,处理器数目是受限的,现实的代价：通讯，同步，,分布式计算,算法的研究,随机算法,判定问题：,以较大概率得到正确输出,输出正确，但计算时间不定,优化问题：输出解的性能不稳定,以较大概率得到性能好的解,算法的研究,完全算法,利用某些策略减少计算量,分支界限法（,Branch and Bound,）,最坏情况时间复杂度是指数的,近似算法,不要最优，只求较优,时间复杂度较低,算法的研究,近似算法,局部搜索,遗传算法,模拟退火,