计算复杂性与智能算法课件.ppt

《计算复杂性与智能算法课件.ppt》由会员分享，可在线阅读，更多相关《计算复杂性与智能算法课件.ppt（97页珍藏版）》请在三一办公上搜索。

1、第3章 计算复杂性与智能算法,第8课 计算复杂性 第9课 近似算法 第10课 智能型算法 第11课 线性规划,第8课 计算复杂性,算法复杂性问题 图灵机 P类与NP类问题 NP完全问题,算法的复杂性问题 算法本身能不能解，这个问题应该在求解问题前就应该首先确定，因为如果一个问题是不可解的，那么对这个问题寻求算法的努力也是徒劳的。问题否可解的相关内容，也就是算法复杂性理论所涉及到的内容。包括P、NP问题的定义以及比较，还有确定型图灵机的介绍。这些内容不足以构成算法复杂性理论体系，但是了解这些内容是复杂性理论深入学习的基础。,计算复杂性问题,可解问题与不可解问题 并不是任何计算问题都能够利用计算机

2、来解决。算法复杂性理论关心的是哪些问题是可以利用计算机来解决的，也就是说是“可解的问题”；哪些问题是在计算机也解决不了的，也就是“不可解的问题”。尽管理论上可解的问题在实际中未必能够找到实现的算法，但算法复杂性理论关心的是如何在理论上证明问题的可解，而不关心具体如何实现。,计算复杂性问题,P问题与NP问题 如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题的集合。通俗地称所有复杂度为多项式时间的问题为易解的问题类，否则为难解的问题。这种可以在多项式时间内验证一个解是否正确的问题称

3、为NP问题,亦称为易验证问题类。,计算复杂性问题,NP理论的核心问题 如果说P问题是NP问题的一个真子集，那么可以不必花太多时间寻找大规模输入NP问题的解，因为这样的努力都是徒劳的；然而如果能够证明NP问题是P问题，那么结果就很不一样了，它说明了现在许多的指数复杂度的问题都有多项式复杂度的解法，只不过是暂时找不到而已。,计算复杂性问题,三种常用计算模型.随机存取机RAM模型.随机存取存储程序机RASP模型.图灵机模型,计算复杂性问题,随机存取机RAM1.RAM的结构,计算复杂性问题,2.RAM程序 一个RAM程序定义了从输入带到输出带的一个映射。可以对这种映射关系作2种不同的解释。解释一：把R

4、AM程序看成是计算一个函数若一个RAM程序P总是从输入带前n个方格中读入n个整数x1，x2，xn，并且在输出带的第一个方格上输出一个整数y后停机，那么就说程序P计算了函数 f(x1，x2，xn)=y,计算复杂性问题,解释二：把RAM程序当作一个语言接受器将字符串S=a1a2an放在输入带上。在输入带的第一个方格中放入符号a1，第二个方格中放入符号a2，第n个方格中放入符号an。然后在第n+1个方格中放入0，作为输入串的结束标志符。如果一个RAM程序P读了字符串S及结束标志符0后，在输出带的第一格输出一个1并停机，就说程序P接受字符串S。,计算复杂性问题,3.RAM程序的耗费标准标准一：均匀耗费

5、标准在均匀耗费标准下，每条RAM指令需要一个单位时间；每个寄存器占用一个单位空间。RAM程序的复杂性一般按照均匀耗费标准衡量。,计算复杂性问题,标准二：对数耗费标准对数耗费标准是基于这样的假定，即执行一条指令的耗费与以二进制表示的指令的操作数长度成比例。在RAM计算模型下，假定一个寄存器可存放一个任意大小的整数。因此若设l(i)是整数i所占的二进制位数，则,计算复杂性问题,随机存取机RASP1.RASP的结构RASP的整体结构类似于RAM，所不同的是RASP的程序是存储在寄存器中的。每条RASP指令占据2个连续的寄存器。第一个寄存器存放操作码的编码，第二个寄存器存放地址。RASP指令用整数进行

6、编码。,计算复杂性问题,2.RASP程序的复杂性不管是在均匀耗费标准下，还是在对数耗费标准下，RAM程序和RASP程序的复杂性只差一个常数因子。在一个计算模型下T(n)时间内完成的输入-输出映射可在另一个计算模型下模拟，并在kT(n)时间内完成。其中k是一个常数因子。空间复杂性的情况也是类似的。,计算复杂性问题,图灵机1、图灵机的构成 图灵机由一个控制器和一条无限长的工作带组成，工作带：划分为许多单元，每个单元可以存放字母表 中的一个符号。控制器：具有有穷个内部状态和一个读写头。,计算复杂性问题,单带图灵机结构,计算复杂性问题,图灵机的工作过程 计算的每一步，控制器处于某个状态，读写头扫描工作

7、带的某一个单元符号；根据当前状态、被扫描单元的内容，决定下一步的执行动作：把当前单元内容，改写成某一个符号；使读写头停止不动、向左或向右移动一个单元；使控制器转移到某一个状态等等。,计算复杂性问题,计算开始时，输入符号串放在工作带上，控制器处于初始状态，读写头扫描输入符号串左端的第一个符号；如果对于当前的状态和所扫描的符号，没有下一步的动作，则图灵机就停止计算。,计算复杂性问题,图灵机形式定义 图灵机 是一个六元组：S：控制器的非空有限状态集合；：有限工作带符号集合，含空白符B；：输入符号字母表，；P0：初始状态，；Pf：最终状态或接受状态，；：转移函数。,计算复杂性问题,转移函数的说明转移函

8、数的定义域：转移函数的值域：,计算复杂性问题,L,P,R 读写头的动作:L:左移一个单元；P:停止不动；R:右移一个单元；转移函数的含义：控制器当前状态为P、读写头扫描到的符号为x 时，把控制器状态修改为P；把符号修改为符号x；使读写头向右移动一个单元。,计算复杂性问题,图灵机格局定义 是一个图灵机，M 的格局是一个二元组：:是工作带上的内容。:表示在此格局下读写头的位置；1:表示处于读写头左边的符号串；2:表示处于读写头右边的符号串。读写头指向符号串2 的第一个符号。,计算复杂性问题,图灵机格局初始格局：，1 为空串；可接受格局：，P 是可接受状态，即。停机格局：中，2 的第一个符号是x，转

9、移函数 没有定义，则称是停机格局。,计算复杂性问题,图灵机的计算 是一个有穷、或无穷的格局序列，如果每一个i+1 都由i 经过一步得到，称这个序列是一个计算。,计算复杂性问题,图灵机计算的停机状态1）计算是有穷序列，是可接受的停机格局，称停机在接受状态。称图灵机 M 接受符号串；2）计算是有穷序列，不是可接受的停机格局，称停机在拒绝状态。称图灵机 M 不接受符号串，或拒绝符号串;3）计算是无穷序列，永不停机。,计算复杂性问题,图灵机对语言的识别构造一个识别语言 的图灵机设计思想：使读写头来回移动，成对地对输入符号串的左端和右端作标记。如果全部符号都作了标记，则左边的与右边的个数相等，；否则，。

10、,计算复杂性问题,图灵机的构造S=P0,P1,P2,P3,P4,PN;=a,b,x,B;=a,b,;Pf=P4,PN;其中，P4 为接受状态，PN 为拒绝状态。,计算复杂性问题,转移函数(p0,a)=(p0,b)=(p1,a)=(p1,x)=(p1,B)=(p2,b)=(p2,x)=(p2,B)=(p3,a)=(p3,x)=(p3,B)=,计算复杂性问题,对于，设n=2，图灵机的工作过程如下：,计算复杂性,计算复杂性问题,计算复杂性问题,K带图灵机结构 有K个工作带，每个工作带有一个读写头，都可以独立地移动。,计算复杂性问题,K带图灵机形式定义转移函数的形式：K带图灵机格局若x是输入符号串，则

11、初始格局表示为,计算复杂性问题,确定的图灵机和非确定的图灵机确定性图灵机 若图灵机的转移函数是单值的，则称该图灵机为确定性图灵机，记为 DTM，图灵机每一步的动作都是确定的。非确定的图灵机 若图灵机的转移函数是多值的，则称该图灵机为非确定性图灵机，记为 NDTM。,计算复杂性问题,图灵机的执行时间图灵机的计算的长度 设 是一个格局序列，它是图灵机对输入的一个计算。如果t 是一个可接受的停机格局，则称这个计算是可接受的计算，t 称为这个计算的长度。,计算复杂性问题,图灵机的执行时间 图灵机M 对输入x进行计算的执行时间，记为TM(x)，它定义为：(1)如果M 对输入x有一个可接受的计算，则TM(

12、x)是最短的可接受计算的长度；(2)如果M 对输入 x没有一个可接受的计算，则 TM(x)=。,计算复杂性问题,图灵机的时间复杂性 图灵机M的时间复杂性T(n)是它处理所有长度为n的输入所需的最大计算步数。如果对某个长度为n的输入，图灵机不停机，T(n)对这个n值无定义。,计算复杂性问题,图灵机的空间复杂性 图灵机的空间复杂性S(n)是它处理所有长度为n的输入时，在k条带上所使用过的方格数的总和。如果某个读写头无限地向右移动而不停机，S(n)也无定义。,计算复杂性问题,图灵机模型与RAM模型的关系 图灵机模型与RAM模型的关系是指同一问题在这两种不同计算模型下的复杂性之间的关系。对于问题P的任

13、何长度为n的输入，设求解问题P的算法A在k带图灵机模型TM下的时间复杂性为T(n)，那么，算法A在RAM模型下的时间复杂性为O(T2(n)。,计算复杂性问题,对于问题P的任何长度为n的输入，设求解问题P的算法A在RAM模型下，不含有乘法和除法指令，且按对数耗费标准其时间复杂性为T(n)，那么，算法A在k带图灵机模型TM下的时间复杂性为O(T2(n)。通过问题变换的技巧，可以将不同问题的计算复杂性联系在一起。这样就可以将一个问题的计算复杂性归结为另一个问题的计算复杂性。,计算复杂性问题,易解的问题和难解的问题存在多项式时间算法的问题，称为易解的问题。指数时间算法或排列时间算法的问题，称为难解的问

14、题。,P类与NP类问题,难解问题的计算相关性计算相关：某类问题可以归约为另一类问题。计算相关问题 若它们之一可用多项式时间求解，则其它同类问题也可用多项式时间求解；若它们之一肯定不存在多项式时间算法，则同类的其它问题，也肯定不会找到多项式时间算法。,P类与NP类问题,P类和NP类语言的定义 P=L|L是一个能在多项式时间内被一台DTM所接受的语言 NP=L|L是一个能在多项式时间内被一台NDTM所接受的语言,P类与NP类问题,判定问题和优化问题判定问题:只牵涉到两种情况：YES 或 NO，可以容易地表达为语言的识别问题，方便在图灵机上进行求解。例如：排序问题的判定问题。给定一个整数数组，是否可

15、以按非降顺序排序；图着色的判定问题。给定无向图，是否可用K种颜色为N中的每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色。,P类与NP类问题,优化问题优化问题牵涉到极值问题。例：图着色的优化问题。为图G着色，使相邻两个顶点不会有相同颜色时所需要的最少颜色数目。,P类与NP类问题,例：求解为图G着色，使相邻两个顶点不会有相同颜色时所需最少颜色数num。令图G的顶点个数为n，彩色数是num，假定存在一个图G着色判定问题的多项式时间算法coloring：BOOL coloring(GRAPH G,int n,int num)则可用下面的方法，利用算法coloring来解图着色的优化问题。

16、,P类与NP类问题,void chromatic_number(GRAPH G,int n,int while(low=high),P类与NP类问题,num=(low+high)/2;if(coloring(G,n,num)low=mid+1;else high=mid 1;num=high;,P类与NP类问题,判定问题转换为优化问题 对算法coloring调用O(log n)次，就能找出为图着色的最优彩色数。根据假定，coloring是多项式时间算法;所以，这个算法也是一个多项式时间算法。,P类与NP类问题,P类问题确定性算法 若A是问题的一个算法。如果在处理问题的实例时，在算法的整个执行过

17、程中，每一步只有一个确定的选择，就说算法A是确定性的算法。含义：算法执行的每一个步骤，都有确定的选择。重新用同一输入实例运行该算法，所得到的结果严格一致。,P类与NP类问题,P类判定问题 如果对某个判定问题，存在着一个非负整数K，对输入规模为n的实例，能够以O(nk)的时间运行一个确定性的算法，得到 YES 或NO 的答案，则该判定问题是一个P类判定问题。特性：P类判定问题是由具有多项式时间的确定性算法来解的判定问题。,P类与NP类问题,例如：最短路径判定问题 给定有向赋权图G（权为正整数）、正整数K、及两个顶点s,t，是否存在着一条由s到t、长度至多为K的路径。可排序的判定问题 给定n个元素

18、的数组，是否可以按非降顺序排序。,P类与NP类问题,P类判定问题的补 改变判定问题的提法，“是否不可以”、“是否不存在”的判定问题。例：可排序判定问题的补 给定n个元素的数组，是否不可以按非降顺序排序。最短路径判定问题的补 给定有向赋权图G（权为正整数）、正整数K、及两个顶点s、t，是否不存在着一条由s到t、长度至多为K的路径。,P类与NP类问题,P类问题的封闭性 令C是一类问题，如果对C中的任何问题C，的补也在C中，则称C类问题在补集下封闭。P类问题的封闭性:P类问题在补集下是封闭的。,P类与NP类问题,归约的定义 令和是两个判定问题，如果存在一个确定性算法A，可以用多项式的时间，把问题的实

19、例I转换为问题的实例I，使得的答案为yes，当且仅当I的答案是yes。就说，以多项式时间归约于，记为p。,P类与NP类问题,P类问题的归约性 和是两个判定问题，如果,P，并且，p，则P。,P类与NP类问题,NP类问题非确定性算法 问题的非确定性算法的分为两个阶段：推测阶段和验证阶段。推测阶段 对规模为n的输入实例x，以多项式时间O(ni)产生输出y，而不管y的正确性。,P类与NP类问题,验证阶段 以多项式时间O(nj)的确定性算法验证两件事情：1）检查上一阶段的输出y是否具有正确的形式。如果y不具正确的形式，算法就以答案no结束；2）如果y具有正确的形式，则继续检查 是否是问题的输入实例x 的

20、解。如果它确实是问题实例x的解，则以答案yes结束，否则，以答案no结束。,P类与NP类问题,旅行售货商的判定问题 给定n个城市、正常数k、及城市之间的费用矩阵C，判定是否存在一条经过所有城市一次且仅一次、最后返回初始出发城市、且费用小于常数k的回路。令A是求旅行售货商判定问题的算法。A用非确定性的方法，在多项式时间内推测存在着一条回路，假定它是问题的解;,P类与NP类问题,A用确定性的算法，在多项式时间内检查：该回路是否是哈密尔屯回路，如果答案为yes，则继续检查该回路的费用是否小于常数C，如果答案仍为yes，则算法A输出yes，否则输出no。因此，A是求解旅行售货商判定问题的非确定性算法。

21、,P类与NP类问题,非确定性算法的运行时间 非确定性算法的运行时间，是推测阶段和验证阶段运行时间的和。若推测阶段的运行时间为O(ni)，验证阶段的运行时间为O(nj)，则对某个非负整数k，非确定性算法的运行时间为O(ni)+O(nj)=O(nk)。,P类与NP类问题,NP类判定问题 如果对某个判定问题，存在着一个非负整数k，对输入规模为n的实例，能够以O(nk)的时间运行一个非确定性的算法，得到yes或no的答案，则该判定问题是一个NP类判定问题。,P类与NP类问题,旅行售货商问题 若算法A可在推测阶段用多项式时间推测出一条回路，并假定它是问题的解；在验证阶段用多项式时间的确定性算法，检查所推

22、测的回路是否恰好每个城市经过一次，如果是，再进一步判断这条回路的长度是否小于或等于L，如果是，答案为yes，否则，答案为no。根据定义，旅行售货商判定问题是NP类判定问题。,P类与NP类问题,P类问题和NP类问题的差别 P类问题可以用多项式时间的确定性算法来进行判定或求解；NP类问题可以用多项式时间的确定性算法来检查和验证它的解。P，必然有NP，所以，P NP。猜测 PNP。该不等式是否成立、至今还没有得到证明。,P类与NP类问题,NP完全问题概念NP难题 令是一个判定问题，如果对NP 中的每一个问题NP，有 p，就说判定问题 是一个 NP难题。,NP完全问题,NP完全问题 令是一个判定问题，

23、如果：(1)NP，并且：(2)对NP中的所有问题NP，都有p；则称判定问题是NP 完全的。NP难题和NP完全问题的差别 是NP完全问题，是NP难题，则必定在NP类中，而不一定在NP 类中。,NP完全问题,NP完全问题的特性 令 和是 NP中的两个问题，使得p。如果是NP完全的，则 也是完全的。NP 完全问题的证明证明下面两件事情：(1)NP，并且：(2)存在一个NP完全问题，使得；p。,NP完全问题,NP完全问题举例 已知哈密尔顿回路问题是一个NP完全问题，证明旅行售货商问题也是一个NP完全问题。哈密尔顿回路问题 给定无向图G，是否存在一条回路，使得图中每个顶点在回路中出现一次且仅一次。,NP

24、完全问题,旅行售货商问题 给定n个城市和最短距离l，是否存在从某个城市出发、经过每个城市一次且仅一次、最后回到出发城市、且距离小于或等于l 的路线。证明旅行售货商问题是NP问题。证明哈密尔顿回路问题 可用多项式时间归约为旅行售货商问题，即 p。,NP完全问题,令G=(V,E)是哈密尔顿回路问题的任一实例，|V|=n。构造赋权图，使得 V=V,E=(u,v)|u,vV。对E中的每一条边u,v 赋予如下的长度：,NP完全问题,令l=n。可以由一个算法在多项式时间里完成这个构造。因此，哈密尔顿回路问题可以用多项式时间归约为旅行售货商问题。(3)证明G中包含一条哈密尔顿回路，当且仅当G 中存在一条经过

25、各个顶点一次，且全长不超过 l=n的路径。,NP完全问题,1.G中包含一条哈密尔顿回路，设这条回路是v1,v2vn,v1。则该回路也是G 中一条经过各个顶点一次且仅一次的回路，根据定义的公式，这条回路长度为n，因此，这条路径满足旅行售货商问题。,NP完全问题,2.G中存在一条满足旅行售货商问题的路径，则这条路径经过G中各个顶点一次且仅一次，最后回到起始出发顶点的回路，因此它是一条哈密尔顿回路。综上所述，哈密尔顿回路问题可用多项式时间归约为旅行售货商问题成立，即 p。所以旅行售货商问题也是一个NP完全问题。,NP完全问题,可满足性问题合取范式 由若干个析取子句的合取构成的布尔表达式 f。例：合取

26、范式的可满足性 对合取范式f的相应布尔变量赋值，使f的真值为真，就说布尔表达式f是可满足的。,NP完全问题,可满足性问题定义判定问题：可满足性问题（SAT）输入：布尔表达式合取范式f（CNF）问题：对布尔表达式f中的布尔变量赋值,是 否可使f的真值为真 Cook定理 可满足性问题是NP 完全的。,NP完全问题,Cook定理的意义 Cook定理给出了第一个NP完全问题，使得对任何问题，只要能够证明 NP，并且 SATp，那么，就是NP完全的。,NP完全问题,三元可满足性问题三元合取范式 在合取范式中，每个析取子句恰好由三个文字组成，称为三元合取范式。三元合取范式的可满足性问题是NP完全问题判定问

27、题：3_SAT输入：三元合取范式f问题：对布尔表达式f中的布尔变量赋值,是否可使f的真值为真,NP完全问题,典型的NP完全问题,NP完全问题,部分NP完全问题树,旅行售货商问题（TSP）问题描述 给定一个无向完全图G=(V，E)及定义在VV上的一个费用函数c和一个整数k，判定G是否存在经过V中各顶点恰好一次的回路，使得该回路的费用不超过k。,NP完全问题,哈密尔顿回路问题（HAM-CYCLE）问题描述 给定无向图G=(V，E)，判定其是否含有一哈密顿回路。证明思路 首先，已知哈密顿回路问题是一个NP类问题。其次，通过证明3-SATpHAM-CYCLE，得出：HAM-CYCLENPC。,NP完全

28、问题,团集问题（CLIQUE）问题描述 给定一个无向图G=(V，E)和一个正整数k，判定图G是否包含一个k团，即是否存在，VV，|V|=k，且对任意u，wV 有(u，w)E。证明思路 已经知道CLIQUENP。通过3-SATpCLIQUE来证明CLIQUE是NP难问题，从而证明团问题是NP完全问题。,NP完全问题,顶点覆盖问题（VERTEX-COVER）问题描述 给定一个无向图G=(V，E)和一个正整数k，判定是否存在V V，|V|=k，使得对于任意(u，v)E有uV或vV。如果存在这样的V，就称V为图G的一个大小为k顶点覆盖。,NP完全问题,证明思路 首先，VERTEX-COVERNP。因为

29、对于给定的图G和正整数k以及一个实例V，验证|V|=k，然后对每条边(u，v)E，检查是否有uV 或vV，显然可在多项式时间内完成。其次，通过CLIQUEpVERTEX-COVER来证明顶点覆盖问题是NP难的。,NP完全问题,子集和问题（SUBSET-SUM）问题描述 给定整数集合S和一个整数t，判定是否存在S的一个子集S S，使得S 中整数的和为t。例如，若S=1，4，16，64，256，1040，1041，1093，1284，1344且t=3754，则子集S=1，16，64，256，1040，1093，1284是一个解。,NP完全问题,证明思路 首先，对于子集和问题的一个实例，给定一个“证

30、书”S，要验证t=是否成立，显然可在多项式时间内完成。因此，SUBSET-SUMNP；其次，证明 VERTEX-COVERpSUBSET-SUM。,NP完全问题,图的着色问题（COLORING）问题描述 给定一个无向图G=(V，E)和一个正整数k，用k种颜色为G中的每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色。归结为：判定问题：COLORING输入：无向图G(V,E),正整数k1问题：是否可用k种颜色为图G着色,NP完全问题,证明：图着色问题是NP完全问题（1）图的着色问题是NP问题 假定，图G有n个顶点，可以在线性时间内，用k种颜色为G中的每一个顶点着色，并假定它就是问题的解

31、；可以在多项式时间内验证该着色是否就是问题的解。因此，图的着色问题是NP问题。,NP完全问题,（2）可用多项式时间把3_SAT问题归约为COLORING问题。设 是3_SAT的一个实例，它具有m个三元析取子句ci，1im，和n个布尔变量x1,x2,xn，且n4。1）把3_SAT问题变换为COLORING问题构造图G(V,E)，使得顶点集V为：其中，yi是新增加的辅助变元。,NP完全问题,对所有的 1i,jn，1km，使边集E为：显然，可以在多项式时间内完成图G的构造。,NP完全问题,2）三元合取范式f可满足，当且仅当图G 可着色。必要性：考察边集，对所有的 1in，yi构成图G的一个完全子图，

32、则yi和yj不能为同一种颜色。若令顶点yi的颜色为i，则由yi构成的完全子图可着色。,NP完全问题,考察边集 及边集,yi和xj、yi和 不能为同一种颜色。若令顶点xi 的颜色为i 或n+1，则由xi和yi构成的导出子图可着色;同理，若令顶点 的颜色为i或n+1，则由 和yi构成的导出子图可着色。,NP完全问题,考察边集，xi和 不能为同一种颜色，若令xi 和 中，一个顶点的颜色为i，另一个顶点的颜色为n+1，则由 xi、和yi 构成的导出子图可着色。,NP完全问题,考察边集 和边集，每个ck，1km，都包含三个命题变元、或命题变元的否定，而n4，因此，每个 ck至少与一对顶点xi、及 相连接

33、，从而，每个顶点ck 的颜色都不能为n+1。,NP完全问题,如果三元合取范式f 可满足，则它的每个三元析取子句 都可满足。令 ck为：其中，u为x或，1km，1r,s,tn，因为ck为真，在ur、us、ut中，必定有一个为真，假定ur为真。令ck的颜色为r，可使与边集、相关联的顶点可着色，从而图G 可着色。,NP完全问题,充分性 若图G可着色，则与边集、相关联的顶点可着色。对所有的k，1km，存在着r，1rn，使得ck的颜色值就是ur的颜色值 r。只要ur的真值为真，ck的真值就为真，而三元合取范式f也为真。,NP完全问题,而ur可能是xr 或，对所有的r，xr 和 不能为同一种颜色。xr和 中，必有一个颜色值为r，另一个颜色值为n+1，ck的颜色值不可能为n+1，这意味着，在三元合取范式 中，使所有f取值为真的的xr和 不能发生矛盾。综上，三元合取范式f是可满足的。由此，3_SAT p COLORING，所以，图着色问题COLORING是NP完全问题。,NP完全问题,本课结束,下课啦，休息一会儿！,