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

第3章计算复杂性与智能算法

第8课计算复杂性第9课近似算法

第10课智能型算法

第11课

线性规划

第3章计算复杂性与智能算法第8课计算复杂性第8课

计算复杂性

•算法复杂性问题

•图灵机

•P类与NP类问题

•NP完全问题第8课计算复杂性•算法复杂性问题

□算法的复杂性问题•算法本身能不能解，这个问题应该在求解问题前就应该首先确定，因为如果一个问题是不可解的，那么对这个问题寻求算法的努力也是徒劳的。问题否可解的相关内容，也就是算法复杂性理论所涉及到的内容。包括P、NP问题的定义以及比较，还有确定型图灵机的介绍。这些内容不足以构成算法复杂性理论体系，但是了解这些内容是复杂性理论深入学习的基础。计算复杂性问题□算法的复杂性问题计算复杂性问题

•可解问题与不可解问题并不是任何计算问题都能够利用计算机来解决。算法复杂性理论关心的是哪些问题是可以利用计算机来解决的，也就是说是“可解的问题”；哪些问题是在计算机也解决不了的，也就是“不可解的问题”。尽管理论上可解的问题在实际中未必能够找到实现的算法，但算法复杂性理论关心的是如何在理论上证明问题的可解，而不关心具体如何实现。

计算复杂性问题•可解问题与不可解问题计算复杂性问题

•

P问题与NP问题如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题的集合。通俗地称所有复杂度为多项式时间的问题为易解的问题类，否则为难解的问题。这种可以在多项式时间内验证一个解是否正确的问题称为NP问题,亦称为易验证问题类。

计算复杂性问题•P问题与NP问题计算复杂性问题

•

NP理论的核心问题如果说P问题是NP问题的一个真子集，那么可以不必花太多时间寻找大规模输入NP问题的解，因为这样的努力都是徒劳的；然而如果能够证明NP问题是P问题，那么结果就很不一样了，它说明了现在许多的指数复杂度的问题都有多项式复杂度的解法，只不过是暂时找不到而已。

计算复杂性问题•NP理论的核心问题计算复杂性问题□三种常用计算模型.随机存取机RAM模型.随机存取存储程序机RASP模型.图灵机模型

计算复杂性问题□三种常用计算模型计算复杂性问题□随机存取机RAM1.RAM的结构

计算复杂性问题□随机存取机RAM计算复杂性问题2.RAM程序一个RAM程序定义了从输入带到输出带的一个映射。可以对这种映射关系作2种不同的解释。解释一：把RAM程序看成是计算一个函数 若一个RAM程序P总是从输入带前n个方格中读入n个整数x1，x2，…，xn，并且在输出带的第一个方格上输出一个整数y后停机，那么就说程序P计算了函数

f(x1，x2，…，xn)=y

计算复杂性问题2.RAM程序计算复杂性问题解释二：把RAM程序当作一个语言接受器 将字符串S=a1a2…an放在输入带上。在输入带的第一个方格中放入符号a1，第二个方格中放入符号a2，…，第n个方格中放入符号an。然后在第n+1个方格中放入0，作为输入串的结束标志符。

如果一个RAM程序P读了字符串S及结束标志符0后，在输出带的第一格输出一个1并停机，就说程序P接受字符串S。

计算复杂性问题解释二：把RAM程序当作一个语言接受器计算复杂性问题3.RAM程序的耗费标准标准一：均匀耗费标准 在均匀耗费标准下，每条RAM指令需要一个单位时间；每个寄存器占用一个单位空间。RAM程序的复杂性一般按照均匀耗费标准衡量。

计算复杂性问题3.RAM程序的耗费标准计算复杂性问题标准二：对数耗费标准 对数耗费标准是基于这样的假定，即执行一条指令的耗费与以二进制表示的指令的操作数长度成比例。在RAM计算模型下，假定一个寄存器可存放一个任意大小的整数。因此若设l(i)是整数i所占的二进制位数，则

计算复杂性问题标准二：对数耗费标准计算复杂性问题□随机存取机RASP1.RASP的结构 RASP的整体结构类似于RAM，所不同的是RASP的程序是存储在寄存器中的。每条RASP指令占据2个连续的寄存器。第一个寄存器存放操作码的编码，第二个寄存器存放地址。RASP指令用整数进行编码。

计算复杂性问题□随机存取机RASP计算复杂性问题2.RASP程序的复杂性

不管是在均匀耗费标准下，还是在对数耗费标准下，RAM程序和RASP程序的复杂性只差一个常数因子。在一个计算模型下T(n)时间内完成的输入-输出映射可在另一个计算模型下模拟，并在kT(n)时间内完成。其中k是一个常数因子。空间复杂性的情况也是类似的。

计算复杂性问题2.RASP程序的复杂性计算复杂性问题□图灵机1、图灵机的构成图灵机由一个控制器和一条无限长的工作带组成，

工作带：划分为许多单元，每个单元可以存放字母表中的一个符号。控制器：具有有穷个内部状态和一个读写头。

计算复杂性问题□图灵机计算复杂性问题单带图灵机结构

计算复杂性问题单带图灵机结构计算复杂性问题图灵机的工作过程计算的每一步，控制器处于某个状态，读写头扫描工作带的某一个单元符号；根据当前状态、被扫描单元的内容，决定下一步的执行动作：把当前单元内容，改写成某一个符号；使读写头停止不动、向左或向右移动一个单元；使控制器转移到某一个状态等等。

计算复杂性问题图灵机的工作过程计算复杂性问题计算开始时，输入符号串放在工作带上，控制器处于初始状态，读写头扫描输入符号串左端的第一个符号；如果对于当前的状态和所扫描的符号，没有下一步的动作，则图灵机就停止计算。

计算复杂性问题计算开始时，输入符号串放在工作带上，控制器处于初始状□图灵机形式定义图灵机是一个六元组：S：控制器的非空有限状态集合；Г：有限工作带符号集合，含空白符B；Σ：输入符号字母表，；P0：初始状态，；Pf：最终状态或接受状态，；δ：转移函数。

计算复杂性问题□图灵机形式定义计算复杂性问题转移函数δ的说明转移函数的定义域：转移函数的值域：

计算复杂性问题转移函数δ的说明计算复杂性问题{L,P,R}读写头的动作:

L:

左移一个单元；

P:

停止不动；

R:

右移一个单元；转移函数的含义：控制器当前状态为P

、读写头扫描到的符号为x

时，把控制器状态修改为P`；把符号修改为符号x`

；使读写头向右移动一个单元。

计算复杂性问题{L,P,R}读写头的动作:计算复杂性问题□图灵机格局定义是一个图灵机，M

的格局是一个二元组：

:是工作带上的内容。↑:表示在此格局下读写头的位置；ω1

:表示处于读写头左边的符号串；ω2

:表示处于读写头右边的符号串。读写头指向符号串ω2

的第一个符号。

计算复杂性问题□图灵机格局定义计算复杂性问题图灵机格局初始格局：，ω1

为空串；可接受格局：，P

是可接受状态，即。停机格局：中，ω2

的第一个符号是x

，转移函数没有定义，则称б是停机格局。

计算复杂性问题图灵机格局计算复杂性问题□图灵机的计算是一个有穷、或无穷的格局序列，如果每一个бi+1

都由бi

经过一步得到，称这个序列是一个计算。

计算复杂性问题□图灵机的计算计算复杂性问题□图灵机计算的停机状态1）计算是有穷序列，是可接受的停机格局，称停机在接受状态。称图灵机M接受符号串ω

；2）计算是有穷序列，不是可接受的停机格局，称停机在拒绝状态。称图灵机M

不接受符号串ω

，或拒绝符号串ω;

3）计算是无穷序列，永不停机。

计算复杂性问题□图灵机计算的停机状态计算复杂性问题□图灵机对语言的识别构造一个识别语言的图灵机设计思想：使读写头来回移动，成对地对输入符号串的左端和右端作标记。如果全部符号都作了标记，则左边的与右边的个数相等，；否则，。

计算复杂性问题□图灵机对语言的识别计算复杂性问题□图灵机的构造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，图灵机的工作过程如下：

计算复杂性对于，设n=2，图灵机的工作过程如

计算复杂性问题计算复杂性问题

计算复杂性问题计算复杂性问题□K带图灵机结构有K个工作带，每个工作带有一个读写头，都可以独立地移动。

计算复杂性问题□K带图灵机结构计算复杂性问题□K带图灵机形式定义转移函数δ的形式：K带图灵机格局若x是输入符号串，则初始格局表示为

计算复杂性问题□K带图灵机形式定义计算复杂性问题□确定的图灵机和非确定的图灵机确定性图灵机若图灵机的转移函数δ是单值的，则称该图灵机为确定性图灵机，记为DTM，图灵机每一步的动作都是确定的。非确定的图灵机若图灵机的转移函数δ是多值的，则称该图灵机为非确定性图灵机，记为NDTM。

计算复杂性问题□确定的图灵机和非确定的图灵机计算复杂性问题□图灵机的执行时间图灵机的计算的长度设是一个格局序列，它是图灵机对输入的一个计算。如果бt

是一个可接受的停机格局，则称这个计算是可接受的计算，t

称为这个计算的长度。

计算复杂性问题□图灵机的执行时间计算复杂性问题图灵机的执行时间图灵机M对输入x进行计算的执行时间，记为TM(x)，它定义为：(1)如果M

对输入x有一个可接受的计算，则TM(x)是最短的可接受计算的长度；(2)如果M

对输入x没有一个可接受的计算，则TM(x)=∞。

计算复杂性问题图灵机的执行时间计算复杂性问题□图灵机的时间复杂性图灵机M的时间复杂性T(n)是它处理所有长度为n的输入所需的最大计算步数。如果对某个长度为n的输入，图灵机不停机，T(n)对这个n值无定义。

计算复杂性问题□图灵机的时间复杂性计算复杂性问题□图灵机的空间复杂性图灵机的空间复杂性S(n)是它处理所有长度为n的输入时，在k条带上所使用过的方格数的总和。如果某个读写头无限地向右移动而不停机，S(n)也无定义。

计算复杂性问题□图灵机的空间复杂性计算复杂性问题□图灵机模型与RAM模型的关系

图灵机模型与RAM模型的关系是指同一问题在这两种不同计算模型下的复杂性之间的关系。对于问题P的任何长度为n的输入，设求解问题P的算法A在k带图灵机模型TM下的时间复杂性为T(n)，那么，算法A在RAM模型下的时间复杂性为O(T2(n))。

计算复杂性问题□图灵机模型与RAM模型的关系计算复杂性问题

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

计算复杂性问题对于问题P的任何长度为n的输入，设求解问题P的算法A□易解的问题和难解的问题

存在多项式时间算法的问题，称为易解的问题。

指数时间算法或排列时间算法的问题，称为难解的问题。

P类与NP类问题□易解的问题和难解的问题P类与NP类问题□难解问题的计算相关性计算相关：

某类问题可以归约为另一类问题。计算相关问题

若它们之一可用多项式时间求解，则其它同类问题也可用多项式时间求解；若它们之一肯定不存在多项式时间算法，则同类的其它问题，也肯定不会找到多项式时间算法。

P类与NP类问题□难解问题的计算相关性P类与NP类问题□P类和NP类语言的定义

P={L|L是一个能在多项式时间内被一台DTM所接受的语言}NP={L|L是一个能在多项式时间内被一台NDTM所接受的语言}

P类与NP类问题□P类和NP类语言的定义P类与NP类问题□判定问题和优化问题判定问题:只牵涉到两种情况：YES或NO，可以容易地表达为语言的识别问题，方便在图灵机上进行求解。例如：排序问题的判定问题。给定一个整数数组，是否可以按非降顺序排序；图着色的判定问题。给定无向图，是否可用K种颜色为N中的每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色。

P类与NP类问题□判定问题和优化问题P类与NP类问题□优化问题优化问题牵涉到极值问题。例：图着色的优化问题。为图G着色，使相邻两个顶点不会有相同颜色时所需要的最少颜色数目。

P类与NP类问题□优化问题P类与NP类问题例：求解为图G着色，使相邻两个顶点不会有相同颜色时所需最少颜色数num。令图G的顶点个数为n，彩色数是num，假定存在一个图G着色判定问题的多项式时间算法coloring：

BOOLcoloring(GRAPHG,intn,intnum)则可用下面的方法，利用算法coloring来解图着色的优化问题。

P类与NP类问题例：求解为图G着色，使相邻两个顶点不会有相同颜色时所需最少颜voidchromatic_number(GRAPHG,intn,int&num){inthigh,low;high=n;low=1;while(low<=high){

P类与NP类问题voidchromatic_number(GRAPHG,num=(low+high)/2;if(coloring(G,n,num))low=mid+1;elsehigh=mid–1;}num=high;}

P类与NP类问题num=(low+high)/2;P类与N□判定问题转换为优化问题对算法coloring调用O(logn)次，就能找出为图着色的最优彩色数。根据假定，coloring是多项式时间算法;所以，这个算法也是一个多项式时间算法。

P类与NP类问题□判定问题转换为优化问题P类与NP类问题□P类问题确定性算法若A是问题∏的一个算法。如果在处理问题∏的实例时，在算法的整个执行过程中，每一步只有一个确定的选择，就说算法A是确定性的算法。含义：算法执行的每一个步骤，都有确定的选择。重新用同一输入实例运行该算法，所得到的结果严格一致。

P类与NP类问题□P类问题P类与NP类问题□P类判定问题如果对某个判定问题∏，存在着一个非负整数K，对输入规模为n的实例，能够以O(nk)的时间运行一个确定性的算法，得到YES或NO的答案，则该判定问题∏是一个P类判定问题。特性：P类判定问题是由具有多项式时间的确定性算法来解的判定问题。

P类与NP类问题□P类判定问题P类与NP类问题例如：最短路径判定问题给定有向赋权图G（权为正整数）、正整数K、及两个顶点s,t，是否存在着一条由s到t、长度至多为K的路径。可排序的判定问题给定n个元素的数组，是否可以按非降顺序排序。

P类与NP类问题例如：P类与NP类问题□P类判定问题的补改变判定问题的提法，“是否不可以”、“是否不存在”的判定问题。例：可排序判定问题的补给定n个元素的数组，是否不可以按非降顺序排序。

最短路径判定问题的补给定有向赋权图G（权为正整数）、正整数K、及两个顶点s、t，是否不存在着一条由s到t、长度至多为K的路径。P类与NP类问题□P类判定问题的补P类与NP类问题□P类问题的封闭性令C是一类问题，如果对C中的任何问题∏∈C，∏的补也在C中，则称C类问题在补集下封闭。P类问题的封闭性:

P类问题在补集下是封闭的。

P类与NP类问题□P类问题的封闭性P类与NP类问题□归约的定义令∏和∏′是两个判定问题，如果存在一个确定性算法A，可以用多项式的时间，把问题∏′的实例I′转换为问题∏的实例I，使得的答案为yes，当且仅当I的答案是yes。就说，∏′以多项式时间归约于∏，记为∏′∝p∏。

P类与NP类问题□归约的定义P类与NP类问题□P类问题的归约性∏和∏′是两个判定问题，如果,∏∈P，并且，∏′∝p∏，则∏′∈P。

P类与NP类问题□P类问题的归约性P类与NP类问题□NP类问题非确定性算法问题∏的非确定性算法的分为两个阶段：推测阶段和验证阶段。推测阶段

对规模为n的输入实例x，以多项式时间O(ni)产生输出y，而不管y的正确性。

P类与NP类问题□NP类问题P类与NP类问题验证阶段以多项式时间O(nj)的确定性算法验证两件事情：1）检查上一阶段的输出y是否具有正确的形式。如果y不具正确的形式，算法就以答案no结束；2）如果y具有正确的形式，则继续检查是否是问题的输入实例x的解。如果它确实是问题实例x的解，则以答案yes结束，否则，以答案no结束。

P类与NP类问题验证阶段P类与NP类问题□旅行售货商的判定问题给定n个城市、正常数k、及城市之间的费用矩阵C，判定是否存在一条经过所有城市一次且仅一次、最后返回初始出发城市、且费用小于常数k的回路。令A是求旅行售货商判定问题的算法。A用非确定性的方法，在多项式时间内推测存在着一条回路，假定它是问题的解;

P类与NP类问题□旅行售货商的判定问题P类与NP类问题A用确定性的算法，在多项式时间内检查：该回路是否是哈密尔屯回路，如果答案为yes，则继续检查该回路的费用是否小于常数C，如果答案仍为yes，则算法A输出yes，否则输出no。因此，A是求解旅行售货商判定问题的非确定性算法。

P类与NP类问题A用确定性的算法，在多项式时间内检查：该回路是否是哈□非确定性算法的运行时间非确定性算法的运行时间，是推测阶段和验证阶段运行时间的和。若推测阶段的运行时间为O(ni)，验证阶段的运行时间为O(nj)，则对某个非负整数k，非确定性算法的运行时间为O(ni)+O(nj)=O(nk)。

P类与NP类问题□非确定性算法的运行时间P类与NP类问题□NP类判定问题如果对某个判定问题∏，存在着一个非负整数k，对输入规模为n的实例，能够以O(nk)的时间运行一个非确定性的算法，得到yes或no的答案，则该判定问题∏是一个NP类判定问题。

P类与NP类问题□NP类判定问题P类与NP类问题□旅行售货商问题若算法A可在推测阶段用多项式时间推测出一条回路，并假定它是问题的解；在验证阶段用多项式时间的确定性算法，检查所推测的回路是否恰好每个城市经过一次，如果是，再进一步判断这条回路的长度是否小于或等于L，如果是，答案为yes，否则，答案为no。

根据定义，旅行售货商判定问题是NP类判定问题。

P类与NP类问题□旅行售货商问题P类与NP类问题□P类问题和NP类问题的差别

P类问题可以用多项式时间的确定性算法来进行判定或求解；

NP类问题可以用多项式时间的确定性算法来检查和验证它的解。∏∈P，必然有∏∈NP，所以，P

NP。

猜测P≠NP。该不等式是否成立、至今还没有得到证明。

P类与NP类问题□P类问题和NP类问题的差别P类与NP类问题□NP完全问题概念NP难题令∏是一个判定问题，如果对NP中的每一个问题∏′∈NP，有∏′∝p∏，就说判定问题∏是一个NP难题。

NP完全问题□NP完全问题概念NP完全问题NP完全问题

令∏是一个判定问题，如果：(1)∏∈NP，并且：(2)对NP中的所有问题∏′∈NP，都有∏′∝p∏；则称判定问题∏是NP完全的。NP难题和NP完全问题的差别∏是NP完全问题，∏′是NP难题，则∏必定在NP类中，而∏′不一定在NP类中。

NP完全问题NP完全问题NP完全问题□NP完全问题的特性令∏和∏′是NP中的两个问题，使得∏′∝p∏。如果∏′是NP完全的，则∏也是∏完全的。NP完全问题的证明证明下面两件事情：(1)∏∈NP，并且：(2)存在一个NP完全问题∏′，使得；∏′∝p∏。

NP完全问题□NP完全问题的特性NP完全问题□NP完全问题举例已知哈密尔顿回路问题是一个NP完全问题，证明旅行售货商问题也是一个NP完全问题。哈密尔顿回路问题给定无向图G，是否存在一条回路，使得图中每个顶点在回路中出现一次且仅一次。

NP完全问题□NP完全问题举例NP完全问题旅行售货商问题给定n个城市和最短距离l，是否存在从某个城市出发、经过每个城市一次且仅一次、最后回到出发城市、且距离小于或等于l的路线。证明旅行售货商问题∏是NP问题。证明哈密尔顿回路问题∏′

可用多项式时间归约为旅行售货商问题，即∏′∝p∏。

NP完全问题旅行售货商问题NP完全问题令G=(V,E)是哈密尔顿回路问题的任一实例，|V|=n。构造赋权图，使得V=V′

,E′={(u,v)|u,v∈V}。对E′中的每一条边u,v赋予如下的长度：

NP完全问题令G=(V,E)是哈密尔顿回路问题的任一实例，|V令l=n

。可以由一个算法在多项式时间里完成这个构造。因此，哈密尔顿回路问题可以用多项式时间归约为旅行售货商问题。(3)

证明G中包含一条哈密尔顿回路，当且仅当G’中存在一条经过各个顶点一次，且全长不超过

l=n的路径。NP完全问题令l=n。NP完全问题1.G中包含一条哈密尔顿回路，设这条回路是v1,v2…vn,v1

。则该回路也是G’中一条经过各个顶点一次且仅一次的回路，根据定义的公式，这条回路长度为n，因此，这条路径满足旅行售货商问题。

NP完全问题1.G中包含一条哈密尔顿回路，设这条回路是v1,v2…vn2.G′中存在一条满足旅行售货商问题的路径，则这条路径经过G中各个顶点一次且仅一次，最后回到起始出发顶点的回路，因此它是一条哈密尔顿回路。综上所述，哈密尔顿回路问题∏′可用多项式时间归约为旅行售货商问题成立，即∏′∝p∏。所以旅行售货商问题也是一个NP完全问题。NP完全问题2.G′中存在一条满足旅行售货商问题的路径，则这条路径经过□可满足性问题合取范式由若干个析取子句的合取构成的布尔表达式

f。例：合取范式的可满足性对合取范式f的相应布尔变量赋值，使f的真值为真，就说布尔表达式f是可满足的。

NP完全问题□可满足性问题NP完全问题□可满足性问题定义判定问题：可满足性问题（SAT）输入：布尔表达式合取范式f（CNF）问题：对布尔表达式f中的布尔变量赋值,是

否可使f的真值为真□Cook定理可满足性问题是NP完全的。

NP完全问题□可满足性问题定义NP完全问题□Cook定理的意义Cook定理给出了第一个NP完全问题，使得对任何问题∏，只要能够证明∏∈NP，并且SAT∝p∏

，那么，∏就是NP完全的。

NP完全问题□Cook定理的意义NP完全问题□三元可满足性问题三元合取范式在合取范式中，每个析取子句恰好由三个文字组成，称为三元合取范式。三元合取范式的可满足性问题是NP完全问题判定问题：3_SAT输入：三元合取范式f问题：对布尔表达式f中的布尔变量赋值,是否可使f的真值为真

NP完全问题□三元可满足性问题NP完全问题□典型的NP完全问题

NP完全问题部分NP完全问题树□典型的NP完全问题NP完全问题部分NP完全问题树□旅行售货商问题（TSP）问题描述

给定一个无向完全图G=(V，E)及定义在V

V上的一个费用函数c和一个整数k，判定G是否存在经过V中各顶点恰好一次的回路，使得该回路的费用不超过k。

NP完全问题□旅行售货商问题（TSP）NP完全问题□哈密尔顿回路问题（HAM-CYCLE）问题描述

给定无向图G=(V，E)，判定其是否含有一哈密顿回路。证明思路首先，已知哈密顿回路问题是一个NP类问题。其次，通过证明3-SAT∝pHAM-CYCLE，得出：HAM-CYCLE∈NPC。

NP完全问题□哈密尔顿回路问题（HAM-CYCLE）NP完全问题□团集问题（CLIQUE）问题描述给定一个无向图G=(V，E)和一个正整数k，判定图G是否包含一个k团，即是否存在，V′

V，|V

′|=k，且对任意u，w∈V’有(u，w)∈E。证明思路已经知道CLIQUE∈NP。通过3-SAT∝pCLIQUE来证明CLIQUE是NP难问题，从而证明团问题是NP完全问题。

NP完全问题□团集问题（CLIQUE）NP完全问题□顶点覆盖问题（VERTEX-COVER）问题描述

给定一个无向图G=(V，E)和一个正整数k，判定是否存在V

′

V，|V′|=k，使得对于任意(u，v)∈E有u∈V′或v∈V′。如果存在这样的V′，就称V′为图G的一个大小为k顶点覆盖。

NP完全问题□顶点覆盖问题（VERTEX-COVER）NP完全问题证明思路首先，VERTEX-COVER∈NP。因为对于给定的图G和正整数k以及一个实例V′，验证|V

′|=k，然后对每条边(u，v)∈E，检查是否有u∈V

′或v∈V

′，显然可在多项式时间内完成。其次，通过CLIQUE∝pVERTEX-COVER来证明顶点覆盖问题是NP难的。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完全问题□子集和问题（SUBSET-SUM）NP完全问题证明思路首先，对于子集和问题的一个实例<S，t>，给定一个“证书”S′

，要验证t=是否成立，显然可在多项式时间内完成。因此，SUBSET-SUM∈NP；其次，证明VERTEX-COVER∝pSUBSET-SUM。NP完全问题证明思路NP完全问题□图的着色问题（COLORING）问题描述给定一个无向图G=(V，E)和一个正整数k，用k种颜色为G中的每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色。归结为：判定问题：COLORING输入：无向图G＝(V,E),正整数k≥1问题：是否可用k种颜色为图G着色

NP完全问题□图的着色问题（COLORING）NP完全问题证明：图着色问题是NP完全问题（1）图的着色问题是NP问题假定，图G有n个顶点，可以在线性时间内，用k种颜色为G中的每一个顶点着色，并假定它就是问题的解；可以在多项式时间内验证该着色是否就是问题的解。因此，图的着色问题是NP问题。

NP完全问题证明：图着色问题是NP完全问题NP完全问题（2）可用多项式时间把3_SAT问题归约为COLORING问题。设是3_SAT的一个实例，它具有m个三元析取子句ci，1≤i≤m，和n个布尔变量x1,x2,…xn

，且n≥4。1）把3_SAT问题变换为COLORING问题构造图G＝(V,E)，使得顶点集V为：其中，yi是新增加的辅助变元。