第四讲完全性理论精选文档.ppt

第四讲完全性理论本讲稿第一页，共四十七页内容o计算的形式描述计算模型o可计算性理论oP类与NP类问题oNP完全性理论oNP完全性的典型例子本讲稿第二页，共四十七页1 理论计算模型图灵机理论计算模型图灵机A.TuringA.Turing在在19361936年介绍了这样一个通用的计算年介绍了这样一个通用的计算模型，该模型具有以下两个性质模型，该模型具有以下两个性质n该模型的每个过程都是有穷可描述的；n过程必须是由离散的、可以机械执行的步骤组成。图灵机是计算机的一种简单数字模型，尽管简图灵机是计算机的一种简单数字模型，尽管简单，但它具有模拟通用计算机的计算能力。为单，但它具有模拟通用计算机的计算能力。为算法和可计算性研究提供了形式化描述工具。算法和可计算性研究提供了形式化描述工具。本讲稿第三页，共四十七页FinitecontrolX1BB.X2XnXi带带（tape）单元格单元格（cell）带符（带符（tape symbol）n 读写头在每一时刻扫描带上的一个单元读写头在每一时刻扫描带上的一个单元n 带有一个最左单元，向右则是无限的。带有一个最左单元，向右则是无限的。n 带的每个单元可容纳一个带符号带的每个单元可容纳一个带符号开始时，最左边开始时，最左边n个单元装着输入（个单元装着输入（n0，n为有限数），它是一个字符为有限数），它是一个字符串，符号都选自串，符号都选自“带符号带符号”的一个子集，即所谓的的一个子集，即所谓的“输入符号集合输入符号集合”。余下的有穷个单元都存放空白符，它是一个特殊的带符号，但余下的有穷个单元都存放空白符，它是一个特殊的带符号，但不是不是输入符号。输入符号。图灵机的基本模型本讲稿第四页，共四十七页图灵机（Turing Machine)o带子可读可写o无限长的带子o读写头可左移右移 有限状态控制器111 111000000 0BBB1本讲稿第五页，共四十七页在一个图灵机的动作中，图灵机根据带头（读写头）所扫描的符号和有限控制器的状态可能作n改变状态n在被扫描的带单元上重新写一个符号，以代替原来写在该单元上的符号.n将带头向左或者右移一个单元。图灵机的工作机制本讲稿第六页，共四十七页图灵机的形式化描述图灵机的形式化描述 有限状态集 有限输入符号集 有限带符号集 转移函数 开始状态 特殊带符:空白符 终态集合q0 Q T B T F Q转移函数转移函数 :Q Q L,R 形式定义形式定义 一个图灵机一个图灵机 TM(Turing machine)是一个七元组是一个七元组 M=(Q,T,q0,B,F).本讲稿第七页，共四十七页其他图灵机模型o“实际的”的图灵机模型n单带图灵机（1TM）n多带图灵机（kTM）n随机存取机（RAM）o“实际的”n单位时间内完成的工作量有一个多项式上界o所有“实际的”计算模型多项式时间等价本讲稿第八页，共四十七页2 P类与NP类问题o算法的时间复杂度（分成二类）n多项式时间n指数时间o可计算与不可计算本讲稿第九页，共四十七页 10 20 30 40 50 60.00001 .00002 .00003 .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.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多项式与指数函数时间比较本讲稿第十页，共四十七页nn2n3n52n3nN1N2N3N4N5N6100N110N24.64N32.5N4N5+6.641000N131.6N210N33.98N4N6+4.19N5+9.97N6+6.29TimecomplexityfunctionWith presentcomputerWith computer100 times fasterWith computer1000 times faster1小时能解决的最大规模本讲稿第十一页，共四十七页指数灾难：计算量的指数增长本讲稿第十二页，共四十七页Non-deterministic algorithmso目前所講的算法都有一個前提假設，就是它的每個運算(operation)的結果都是獨一(確定)的。這種性質的算法可以在實際的電腦上執行，稱為 deterministic algorithms.o在討論計算理論時，可以將這種限制拿掉，也就是可以假設一個運算的結果不唯一，可能是某 n 個結果中的一個，而且一定會是正確的那一個。這樣子的算法稱為 non-deterministic algorithm。這種算法無法在實際的電腦上執行。本讲稿第十三页，共四十七页o我們定義下列三個涵數來說明這種算法。nChoice(S):從 S 中選一個正確的答案來(若正確答案存在的話)。nFailure():沒有成功地完成工作。nSuccess():成功地完成工作o這三個涵數的執行時間都是 O(1)。o只有在不可能有正確答案的情形下，non-deterministic algorithm 才無法成功地完成工作。o一個可以執行 non-deterministic algorithm 的機器稱為 non-deterministic machine.本讲稿第十四页，共四十七页Example 1 searchingoA1:n 是一個 n 個元素的集合，要在 A 中搜尋一個元素 x 的 non-deterministic algorithm 如下：int j=Choice(1,n);if(Aj=x)cout j;Success();cout 0;Failure();o因為 Choice(1,n)一定會找出一個正確的值，所以拿它找出來的值 j 來比較 Aj=x 若不成立的話，就表示 x 不在 A 裡面。Time complexity 是 O(1)。本讲稿第十五页，共四十七页Example 2 Sortingo要將 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 complexityO(n)本讲稿第十六页，共四十七页o要如何來看待 non-deterministic algorithm 呢？o可以用平行處理的角度來看，也就是當作同時有很多很多機器一起作同一個問題，每個機器用不同的 choice 的結果來作，若有一個成功的話，其他的就不用再作；若某個失敗、就自己停下來即可。o另外更好的解釋是，實際上可能有一種方法可以選擇一個正確的答案出來(只要正確答案存在)，只是我們還不曉得而已（上帝知道），Choice(S)就代表可以找到 S 中正確答案的函數(若正確答案存在)。若正確答案不存在的話，Choice(S)還是會找出一個答案，所以我們需要確認此答案是否正確。本讲稿第十七页，共四十七页Definition oAny 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.oAny 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)o猜想阶段o验证阶段 有限状态控制器111 111000000 0BBB1猜想模块本讲稿第十九页，共四十七页非确定型图灵机的形式化非确定型图灵机的形式化 有限状态集 有限输入符号集 有限带符号集 转移函数 开始状态 特殊带符:空白符 终态集合q0 Q T B T F Q转移函数转移函数 :可随机选择可随机选择 形式定义形式定义 一个非确定型图灵机一个非确定型图灵机 TM 是一个七元组是一个七元组 M=(Q,T,q0,B,F).本讲稿第二十页，共四十七页P类（Polynomial)oP类n具有多项式时间算法的判定问题形成的计算复杂性类n在确定型图灵机上多项式时间可解的问题本讲稿第二十一页，共四十七页NP类(Nondeterministic Polynomial)oNP问题：n在非确定型图灵机上多项式时间可解的问题n在确定型图灵机上多项式时间可验证的问题oP类包含于NP类中oNP类问题在确定图灵机上指数时间可解n非确定型图灵机和确定型图灵机的计算能力相当本讲稿第二十二页，共四十七页Commonly believed relationship between P and NPo一般相信 P P 與 NPNP 兩集合不相同，也就是相信有些問題是屬於 NPNP 而不屬於 P P，但目前仍然無法證明。oCook 曾問過一個問題：有沒有什麼問題應該屬於 NPNP 而不屬於 P P，如果該問題屬於 P P 的話，就表示 P P=NPNP 呢？P PNPNP本讲稿第二十三页，共四十七页Satisfiability ProblemoGiven a Boolean formula(with variables and Boolean operators AND,OR and NOT),is it satisfiable?nIs there an assignment of values 0 or 1 to variables so that the formula evaluates to 1?oConjunctive Normal Form(CNF)nA clause is the OR of some literalsnA Boolean formula consisting of several clauses separated by AND is a CNF formulaoE.g.,(a+b+c)(b+d+e+f)(a+e)本讲稿第二十四页，共四十七页Satisfiability Problem contdo3-CNF:a CNF formula in which each clause has 3 literalsnE.g.,(a+b+c)(d+e+f)(a+f+g)oGiven a 3-CNF formula,is it satisfiable?nThat is,is there an assignment(to variables)that evaluates the formula to 1nThis 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;o這個演算法的 time complexity 是 O(n)再加上 E(x,n)的時間，計算 propositional formula 值的時間與該 formula 的長度有關。o這是第一個被證明為 NP-complete 的問題。本讲稿第二十六页，共四十七页oCook 自己提出一個答案，就是下面的定理。Theorem cookSatisfiability is in P if and only if P P=NPNP.o satisfiability 是第一個 NP-complete 的問題。o要定義 NPNP-hard 與 NPNP-complete 之前，我們需要再定義一個名詞：reducibility.本讲稿第二十七页，共四十七页oLet 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 polynomial time algorithm using a deterministic algorithm that solves L2 in polynomial time.o只要 L2 有 polynomial time 演算法，則 L1 也存在 polynomial time 演算法。o例如 L1 是從 n 個數字中找出最大的數字，而 L2 是將 n 個數字中第 k 大的數字找出來，而 L3 是將 n 個數字作排序，則 L1 L2 L3。本讲稿第二十八页，共四十七页Definition oA 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 PNPNP-hardNP-complete本讲稿第二十九页，共四十七页o同一個問題的 decision 版本與 optimization 版本常常可以互相 reduce，像 max clique其實 reducibility 還有更多種定義。oHalting problem 是一個 NP-hard 的問題，因為 satisfiability 的問題可以 reduce 成 halting problem。Halting problem 的問題是輸入一個演算法 A 與此 A 的 input I，決定 A 輸入 I 時會不會停(或者進入無窮迴圈)。這個問題是 undecidable(無法決定的)，也就是不存在任何(時間複雜度的)演算法來解決這個問題，所以這個問題不屬於 NP。本讲稿第三十页，共四十七页o接下來證明 satisfiability halting problem，寫一個演算法 A，A 的 input 是 propositional formula X，若 X 中有 n 個變數，則測試 2n 種組合，若其中有一種使 X 為 true 的話，A 就停止；否則 A 就進入無窮迴圈。o以這個 A 與 X 當作 halting problem 的輸入，如果 halting problem 的回答是會停，則 satisfiability 的答案就是 yes，若 halting problem 的回答是不會停，則 satisfiability 就是 no。因此 halting problem 若有 polynomial time 演算法的話、satisfiability 同樣有polynomial time 演算法。故得證。本讲稿第三十一页，共四十七页Definition oTwo problems L1 and L2 are said to be polynomially equivalent iff and.o要證明一個問題 L2 是 NP-hard 的話，較簡單的作法是找一個已知的 NP-hard 問題 L1，證明。因為reducible 是有遞移性的，所以 satisfiability o要證明一個NP-hard decision problem 是 NP-complete,只要找出它的polynomial time non-deterministic algorithm 即可本讲稿第三十二页，共四十七页NP完全问题o第一个NP完全问题（Cook定理 1971）n可满足性问题是NP完全问题o六个NP完全问题（Karp 1972)n3SAT，3DM，VC，团，HC，划分o更多的NP完全问题n1979年：300多个n1998年：2000多个本讲稿第三十三页，共四十七页一些典型的NP完全问题o团问题oSubset Sum oSatisfiabilityoHamiltonian CycleoTraveling Salesperson本讲稿第三十四页，共四十七页Example Maximum cliqueoA maximal complete sub-graph of a graph G=(V,E)is a clique.其 clique 的大小就看此 clique 的點數。omax clique problem 是一個 optimization problem，找出一個圖形最大的 clique。o這個問題也可以有 decision的版本，就是 G 的 clique 之大小會不會比數字 k 還大。(輸入：G 與 k)o如果 optimization problem 可以 g(n)的時間內作出來，則 decision 版本也可以在 g(n)時間內作好。o如果 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本讲稿第三十六页，共四十七页Satisfiabilityo令 x1,x2,代表 boolean variables，而 代表 xi 的相反。oA formula 是這些布林變數與 logic AND、logic OR 的組合。oConjunctive normal form(CNF)oDisjunctive normal form(DNF)oThe satisfiability problem is to determine whether a formula is true for some assignment of truth values to the variables.oCNF-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;o這個演算法的 time complexity 是 O(n)再加上 E(x,n)的時間，計算 propositional formula 值的時間與該 formula 的長度有關。o這是第一個被證明為 NP-complete 的問題。本讲稿第三十八页，共四十七页Graph Coloring ProblemoGiven a graph,how to color vertices so that adjacent ones have different colorsnChromatic number is the smallest number of colors needed to color a graphoThe graph coloring problemnOptimization problem:Given a graph G=(V,E),find the chromatic numbernDecision problem:Given a graph G=(V,E)and an integer k,is G k-colorable?本讲稿第三十九页，共四十七页Subset Sum ProblemoGiven a set S of positive integers and an integer k oIs there a subset R of S such that the sum of the elements in R is equal to k?oExamplenS=1,16,64,256,1040,1041,1093,1284,1344 and k=3754nR=1,16,64,256,1040,1093,1284 is a solution本讲稿第四十页，共四十七页Hamiltonian Path ProblemoA Hamiltonian path of a graphnA simple path that passes through every vertex exactly onceoDoes a given undirected graph has a Hamiltonian path?oCan also specify for directed graphs本讲稿第四十一页，共四十七页Traveling Salesperson ProblemoKnown as TSP or minimum tour problemoA salesperson wants to minimize total traveling cost(distance or time)required to visit a set of cities and return to the starting pointoGiven a weighted,complete graph and an integer k,is there a Hamiltonian cycle with total weight at most k?本讲稿第四十二页，共四十七页如何处理NP完全问题 实际的问题不会消失本讲稿第四十三页，共四十七页并行计算o以硬件设备换取时间n存在着很多种并行计算模型n理想模型PRAM可多项式时间解NP完全问题o实际中效果不好n处理器数目是受限的n现实的代价：通讯，同步，o分布式计算本讲稿第四十四页，共四十七页算法的研究o随机算法n判定问题：o以较大概率得到正确输出o输出正确，但计算时间不定n优化问题：输出解的性能不稳定o以较大概率得到性能好的解本讲稿第四十五页，共四十七页算法的研究o完全算法n利用某些策略减少计算量o分支界限法（Branch and Bound）n最坏情况时间复杂度是指数的o近似算法n不要最优，只求较优n时间复杂度较低本讲稿第四十六页，共四十七页算法的研究o近似算法n局部搜索n遗传算法n模拟退火 本讲稿第四十七页，共四十七页