NP完全性理论课件.ppt

第七章 NP完全问题导引,算法设计与分析The Design & Analysis of Computer Algorithms）,第七章 NP完全问题导引算法设计与分析,问题、算法、复杂性和难解性 NP完全理论的基本概念,本章主要内容,前一页,问题、算法、复杂性和难解性 本章主要内容前一页,前一页,概述,在过去大量的研究中，有些问题的算法，以多项式复杂性为界；而有些问题，虽经长期努力，仍找不出以多项式为界的算法，而且也不能证明不存在多项式为界的算法。这些问题不少，构成了一个问题的类。 多项式算法称为有效的算法，否则就是无效的算法。例如，货郎担问题等。,前一页概述 在过去大量的研究中，有些问题的,前一页,概述,可以求解问题的复杂性分为三大类。第一类：存在多项式算法的问题。第二类：肯定不存在多项式算法的问题。第三类：未找到多项式算法，也不能证 明不存在多项式算法的问题。,前一页概述可以求解问题的复杂性分为三大类。,前一页,概述,第三类介于第一类与第二类之间，随着科学技术和理论研究的发展，第三类将会向第一类和第二类分化。 在第三类中有一个子类，这个子类中的问题关系非常密切，只要有一个问题被确定属于第一类或第二类，则该子类的问题也均属于同一类。这一类问题被称为NP完全类，至今已证明这类问题已有1000多个，而且还在不断增加。,前一页概述 第三类介于第一类与第二类之间，随着科学技术和,前一页,概述,当我们通过努力仍然找不到一个问题的多项式算法时，应该考虑这个问题是否NP完全的。NP完全性理论提供了简单有效的方法来证明一个问题与已知的NP完全问题一样难。 当证明了一个问题是NP完全的之后，主要精力就不要放在寻求最优解和精确解之上，而是去寻求满意、可行的解。,前一页概述 当我们通过努力仍然找不到一个问题的多项式算法,前一页,问题算法复杂性难解性,一个问题是指需要回答的一般性提问。问题通常会有若干参数和变量。当这些参数指定了具体的值时，便成为问题的一个实例（Instant）。 若一个算法可以应用于问题的实例I，并能得到I的解，则称该算法解问题。,问 题,前一页问题算法复杂性难解性 一个问题是指需要回答的一般性,前一页,问题算法复杂性难解性,例：TSP问题。一般陈述： 给定C=c1,c2,cm ，d(ci,cj) 找一个排列c1,c2,cm Mind(c1,c2)+d(c2,c3)+d(cn,c1) 实 例： C=c1,c2,c3,c4；d(c1,c2)=7，d(c1,c3)=9， d(c1,c4)=6，d(c2,c3)=5，d(c2,c4)=3，d(c3,c4)=8； 排列 c1,c4,c2,c3 是一个解。,问 题,前一页问题算法复杂性难解性例：TSP问题。问 题,前一页,问题算法复杂性难解性,为了度量一个算法的时间复杂性，需要选择一个编码系统来描述问题的实例，并选择一个计算的模型。只有当编码系统和计算模型确定之后，才能确定时间的复杂度。 多项式算法是划分问题类的标准，如果一个问题是不可用多项式算法求解的，则该问题是难解的。一个问题的难解性是问题固有的性质。它与所选的编码和计算模型无关。即不管如何选择编码和计算模型，都找不到多项式算法。,复杂性,前一页问题算法复杂性难解性 为了度量一个算法的时间复杂,前一页,问题算法复杂性难解性,编码系统：描述问题的符号集和规则。例：TSP的编码 字母表=c,(,),/,0,1,2,3,9 编码 “c（1）c（2）c（3）c（4）/7/9/6/3/5/8 /” 长度31,复杂性,前一页问题算法复杂性难解性编码系统：描述问题的符号集和规则。,前一页,问题算法复杂性难解性,不同的编码系统，对同一个问题的实例的编码长度应该是多项式相关的。 设编码系统 e1 的编码长度为n，存在n的一个多项式P(n)，编码系统e2的编码长度是P(n)，称之为多项式相关。 多项式的和、多项式的积都是多项式，这样的编码系统不会影响算法复杂性的为多项式性质。 例如：某问题在e1编码下的算法时间复杂性是多项式T(n)。在e2编码下，算法不变，算法时间复杂性T(P(n),也是一个多项式。,复杂性,前一页问题算法复杂性难解性 不同的编码系统，对同一个问题,前一页,问题算法复杂性难解性,一个问题的难解性是问题固有的性质。多项式算法是划分问题类的标准，如果一个问题是不可用多项式算法求解的，则该问题是难解的。 ATuning(图灵)证明了有些问题困难到“不可判定”的程度。如停机问题，平面铺砖问题等。,难解性,前一页问题算法复杂性难解性 一个问题的难解性是问题固有的,前一页,问题算法复杂性难解性,不可判定难解问题。可判定难解问题：这种问题甚至用“非确定型图灵机”也不能在多项式时间内求解。可证难解问题：不可判定的难解问题和可判定的难解问题的统称。,难解性,前一页问题算法复杂性难解性不可判定难解问题。难解性,前一页,问题算法复杂性难解性,P类：用确定型图灵机可以在多项式时间内求解的问题。NP类：用非确定型图灵机可以在多项式时间内求解的问题。NPC ：NP完全类。,难解性,前一页问题算法复杂性难解性P类：用确定型图灵机可以在多项式时,前一页,问题算法复杂性难解性,难解性,多项式归约：若能在多项式时间内把问题A的算法变换为问题B的算法，则称问题A多项式归约到问题B。这是NP完全性理论最重要的概念。1971年，Cook证明了在NP类中有一个被称为“可满足性问题”具有如下性质：NP类中的所有其他问题都可以多项式归约到这个问题。如果可满足性问题可以用多项式算法求解，那么NP类中的所有问题都可以用多项式算法解决。如果NP类中的某个问题是难解的，那么可满足性问题也是难解的。,前一页问题算法复杂性难解性难解性多项式归约：若能在多项式时间,前一页,问题算法复杂性难解性,难解性,在Cook之后，人们证明了许多问题和可满足问题一样难（1000多个），称为NP完全类问题（NPComplete problem，NPC）。NPC是当代数学与计算机科学中尚未解决的最重要的问题之一。尽管大多数研究者猜测NP完全问题是难解的，但在证明或否定这个猜测方面几乎没有取得什么进展。,前一页问题算法复杂性难解性难解性,前一页,术语,问题：ProblemNP完全：NPComplete多项式：Polynomial多项式时间界：Polynomialtimebounded多项式相关：Polynomially related 复杂性：Complexity编码系统：Coding system难解性：Hard多项式归约：Polynomial transform确定型图灵机： Deterministic Turing Machine(DTM)非确定型图灵机：Nondeterministic Turing Machine(NDTM),前一页术语问题：Problem,前一页,NP完全理论基本概念,判定问题与语言,判定问题：只有两种可能的解，回答“是”（Y）或者 “非”（N）。 规定问题由实例集合D中回答“是”的实例子集YD组成。 问题的标准格式由两部分构成：用各种分量（集合，图，函数等）规定该问题的一般实例；陈述根据这个实例提出的肯定 否定问题。 NP完全性只考虑判定问题，是因为与语言有关，而语言便于从数学上研究。一般优化问题都可以转换为判定问题。,前一页NP完全理论基本概念 判定问题与语言 判定问题：,前一页,NP完全理论基本概念,判定问题与语言,例：TSP问题。实例： 给定C=c1,c2,cm d(ci,cj)，B R+陈述： 是否存在排列 c1,c2,cm 使d(c1,c2)+d(c2,c3)+d(cn,c1) B,前一页NP完全理论基本概念 判定问题与语言例：TSP问题。,前一页,NP完全理论基本概念,判定问题与语言,判定问题的编码系统e提供了一种方法，用某个字母表上的字符串描述的每一个实例。于是和e把划分成三类： 不是的实例的编码。 回答为“是”的实例的编码。 回答为“否”的实例的编码，记为,L，e=*, 是e的字母表，是实例IY在e下的编码 ,前一页NP完全理论基本概念 判定问题与语言 判定问题,前一页,NP完全理论基本概念,判定问题与语言,设每个判定问题都伴随着一个与编码无关的长度函数 Length : DZ+ 若e和e是的两个合理的编码系统，则的性质对L，e 和L ，e同时成立，或同时不成立。 合理编码系统得到的输入长度“多项式相关”是对的任何合理的编码系统e，存在两个多项式P和P,使若ID，是I在e下的编码，则有 Length I P（） P（Length I）,前一页NP完全理论基本概念 判定问题与语言 设每个判定问,前一页,NP完全理论基本概念,DTM 是分析复杂性的一种计算模型。 DTM 由有限状态控制器，读写头和一条（或多条）无限长的带组成。带上有许多方格，每个方格可以记录一个符号。,确定型图灵机与 P类,前一页NP完全理论基本概念 DTM 是分析复杂性的一,前一页,NP完全理论基本概念,DTM形式地定义（Q，q0 ，Qf） Q ： 有穷状态集 ： 输入符号集 ： 有穷符号集 ：空格符， q0 ：初始状态Qf ：包含两个停机状态qy和qn ：（Qf - qy ，qn)QR,S,LR,S,L分别为:右,停,左,确定型图灵机与 P类,前一页NP完全理论基本概念 DTM形式地定义（Q，,前一页,NP完全理论基本概念,DTM的执行过程如下: 1.开始时，将*中的字符串放在从1到的方格中，其它地方放空格符，控制器处在q0状态。 2.读写头扫描第一个方格中的符号a0，转移函数 (q0,a0)= (q1,a1,)根据事先设计好的函数表 将当前状态改变为q1 在当前格中将a0改写为a1 根据=R,S, L确定读写头向右(R),向左(L) ，或不动(S) (一般为(qi,ai) = (qi+1,ai+1,) 3.直至当前状态q为qy 或qn,计算停止， 若q= qy,答案是“肯定”,DTM接受； 若q= qn,答案是“否定”,DTM拒绝。 4.每个步骤即为一步计算。,确定型图灵机与 P类,前一页NP完全理论基本概念 DTM的执行过程如下:确定型图灵,前一页,NP完全理论基本概念,若DTM对输入字符串经过一系列计算后停机在qy状态则称DTM机接受字符串。定义 Lm= *, DTM接受 若DTM,M对输入的字母表上的所有字符串都停机，并且Lm=L，e，则称M在编码系统e下解决判定问题。,确定型图灵机与 P类,前一页NP完全理论基本概念 若DTM对输入字,前一页,NP完全理论基本概念,若存在多项式P，对所有n*，Tm（n）P（n），则M称为多项式时间的DTM。P类语言定义如下： P = L 存在多项式时间的DTM M使得 L=Lm 若L，eP，则称判定问题属于P类。,一个DMT对输入的计算，从开始到停机状态所需的计算步骤，称为该DMT计算所用的时间。M的时间复杂性函数Tm定义为：,Tm（n）=maxm 存在*，=n，M对输入所需计算时间为m,确定型图灵机与 P类,前一页NP完全理论基本概念 若存在多项式P，对所有n,前一页,NP完全理论基本概念,并非每一个问题都可以用DTM在多项式时间内求解。我们假定对某个问题的一个具体实例，可以“猜想”到一个结构，然后对这个结构进行检验。猜想和检验两个阶段构成非确定算法。 给定判断问题的一个实例I，第一阶段猜想出某个结构S，然后把I和S作为检查阶段的输入，检查阶段以普通的确定型方式进行计算，最后停机于qy，qn；或不停地计算下去。,非确定型图灵机与 NP类,前一页NP完全理论基本概念 并非每一个问题都可以用D,前一页,NP完全理论基本概念,例：TSP问题实 例： C=c1,c2,c3,c4；d(c1,c2)=7，d(c1,c3)=9， d(c1,c4)=6，d(c2,c3)=5，d(c2,c4)=3，d(c3,c4)=8。 使d(c1,c2)+d(c2,c3)+d(c4,c1) 24。1、猜想：任一序列c1,c3,c2,c4 是一个结构；2、检验：用 DTM 检查回路是否符合要求，并计算出回路长度。,非确定型图灵机与 NP类,前一页NP完全理论基本概念 例：TSP问题非确定型图灵机,前一页,NP完全理论基本概念,如果对所有的实例ID，下述两条性质成立，则称非确定型算法解判定问题。 1、如果IY，则存在结构S,使得当对输入I和猜想S时，检查阶段对I和S的答案是“肯定”。 2、如果IY，则不存在结构S,使得当对输入I和猜想S时，检查阶段对I和S的答案是“肯定”。 如果存在多项式P使得对每个实例IY，有猜想S导致确定型的检查阶段在时间P（Length I）内回答“肯定”，则称这个非确定型算法是多项式的。,非确定型图灵机与 NP类,前一页NP完全理论基本概念 如果对所有的实例ID,前一页,NP完全理论基本概念,所有可以用非确定型多项式时间算法求解的判定问题构成的类定义为NP类。 “非确定型多项式算法”主要是强调多项式时间可验证，而不是解判定问题的实际方法。 例：货郎担问题，子图同构构问题等都属于NP类。,非确定型图灵机与 NP类,前一页NP完全理论基本概念 所有可以用非确定型多项式,前一页,NP完全理论基本概念,非确定型单带图另机（NDTM），其结构与DTM基本相同，只是多了一个猜想模块和一个只写头。 NDTM形式地定义为（Q，q0 ，Qf）,非确定型图灵机与 NP类,前一页NP完全理论基本概念 非确定型单带图另机（ND,前一页,NP完全理论基本概念,NDTM对输入串的计算分为两个阶段： 1、猜想：开始时在带方格1到中写入输入字符串，读写头扫描方格1，只写头扫描方格-1，有限控制器处于“休眠状态”。然后，猜想模块每次一步通过只写头，或在它所扫描的方格中写入的一个符号（从中任意选的符号，可以写出*中的任意串），并向左移动一格；或停止运动，此时猜想模块进入“休眠状态”。有限状态控制器变成处于q0状态下的活动状态。 2、检验：当有限状态控制器处于q0，检查阶段开始，执行规则与DTM相同，猜想阶段写下的字符串在检查阶段将被检查到。,非确定型图灵机与 NP类,前一页NP完全理论基本概念 NDTM对输入串的计算分为两,前一页,NP完全理论基本概念,有限状态控制器进入停机状态（qy或qn）时，计算停止。若停机在qy，则称此计算为接受计算；若停机在qn，或不停机的计算称为拒斥计算。 NDTM M 对给定的输入字符串有无穷多个可能的计算，而对*中每一个猜想字符串只有一个计算。如果在这些计算中至少有一个是接受计算，则称此NDTM M 接受，可定义 M 识别的语言为： Lm= * NDTM M接受,非确定型图灵机与 NP类,前一页NP完全理论基本概念 有限状态控制器进入停机状态,前一页,NP完全理论基本概念,NDTM M对输入字符串的所有接受计算经过猜想阶段和计算阶段直到进入停机状态qy时，所需的最少步数，称为M接受所需要的时间。Tm（n）定义为：,Tm（n）= 1 m 存在Lm，=n,使得NDTM M 接受所需要的时间为m,若没有长度为n的输入被NDTM M接受，则定义Tm（n）= 1 若存在多项式P使得Tm（n）P（n），则称此NDTM M是一个多项式的NDTM。,非确定型图灵机与 NP类,前一页NP完全理论基本概念 NDTM M对输入字符串,前一页,NP完全理论基本概念,一个判定问题D在NDTM上多项式时间内被解决是指： 对于问题D存在多项式P，使得对于D输入长度为n的实例，若答案为“肯定”，则存在一个猜想，机器在P（n）时间内停机于qy状态；若答案是“否定”，则对于每个猜想，在P（n）时间内停机于q n状态。 如果L，eNP，则称判定问题在编码系统e下属于NP。,非确定型图灵机与 NP类,前一页NP完全理论基本概念 一个判定问题D在NDT,前一页,NP完全理论基本概念,事实上，只是相信存在这么一个猜想，但并未给出用什么方法可以找到这个猜想。即使侥幸碰到了这个猜想，则要逐个验算猜想。而可能的猜想有P(n)-1个 ，要用P(n) P(n)-1d时间来完成，随着P（n）的增长，这是一个可怕的天文数字。所以用这种方法来解决问题是不可能的。,非确定型图灵机与 NP类,前一页NP完全理论基本概念 事实上，只是相信存在这么,前一页,NP完全理论基本概念,能用多项式算法解决的每一个判定问题也能用非确定型多项式算法解决。 如果P，A是关于的确定型的多项式算法，我们只需要用A作为检查阶段，而不管猜想阶段就能得到一个关于的非确定算法，即：PNP，PNP 反之，若NP，则存在一个多项式P使得能用时间复杂度为O（2p(n)）的确定型算法解决。,P与NP,前一页NP完全理论基本概念 能用多项式算法解决的每一,前一页,NP完全理论基本概念,P=NP？虽然经过长期不懈的努力，对NP中的许多问题，如货郎担，子图同构等问题仍未找到多项式算法。一个广泛的概念是PNP。 若PNP，那么NP-P是很重要的。P中问题可用多项式求解，而NP-P中的问题是难解的。,P与NP,前一页NP完全理论基本概念 P=NP？虽然经过长期不,前一页,NP完全理论基本概念,多项式变换： 从语言L1 1*到L2 2*的多项式变换是满足下述两个条件的函数 f: 1* 2* 1、存在一个计算f的多项式时间DTM 2、对所有的1* ， L1 iff f()L2。 从L1多项式变换到L2记为L1L2 。,P与NP,前一页NP完全理论基本概念 多项式变换： P,前一页,NP完全理论基本概念,引理1：若为L1 L2，则L2P L1P （或L1P L2 P）证：设变换多项式f: 1* 2* 计算的f 的DTM为Mf 识别L1，L2，的DTM分别是M1和M2 用合成Mf和M2的方法构造识别L1的多项式DTM。 对输入L1 ，先用Mf构造出f() 2* ，然后利用M2确定f()是否属于L2。由L1 iff f()L2 ，可得到识别L1的DTM程序。由于M1和M2都是多项式的，可得上述算法也是多项式的。,P与NP,前一页NP完全理论基本概念 引理1：若为L1 L2，则L2,前一页,NP完全理论基本概念,从判定问题1到2的多项式变换函数 f: D1 D2 满足 1、存在一个计算f的多项式时间； 2、对所有的ID1 ，IY1 iff f(I)Y2 。 例：HC TSP（H 回路为 HC）,P与NP,前一页NP完全理论基本概念 从判定问题1到2的多项,前一页,NP完全理论基本概念,引理2：若L1 L2且 L2 L3 ，则L1L3。 定义：如果LNP，且对其它所有L NP都有LL则称L是NP完全的。 如果判定问题NP,并且对其他所有判定问题NP都有，则称是NP完全的。 引理3 ：若L1，L2 NP，L1是NP完全的，且L1 L2 ，则L2也是NP完全的。,P与NP,前一页NP完全理论基本概念 引理2：若L1 L2且,前一页,NP完全理论基本概念,判定一个问题是否NP完全的重要方法 只要知道是NP完全的，可用下述步骤证明也是NP完全的： 1、证明NP； 2、找到多项式变换。,P与NP,前一页NP完全理论基本概念 判定一个问题是否NP完全的重要方,前一页,NP完全理论基本概念,1971年，Steven.Cook年找到了第一个NP完全问题，布尔代数的一个判定问题，称为可满足性问题。称为SAT。 Cook定理：SATNPC。 这是NP完全问题的第一个种子，其它的NP完全问题通过SAT得到。 例：1、证明TSPNP； 2、找到多项式变换，使TSP SAT。,P与NP,前一页NP完全理论基本概念 1971年，Steven,前一页,术语,判定问题：Decision Problem猜想阶段：Guessing Phase检验阶段：Verify Phase肯定：Yes否定：No接受：Accepting拒斥：RefuseSAT：Satisfiability Problem,前一页术语判定问题：Decision Problem,前一页,本章结束,前一页本章结束,