（精选）NP完全问题(纯理论).ppt

1、第十二章 NP完全问题,1,12.1 什么是好算法？,算法的种类和数量积累到一定程度时，需要对算法进行比较和分类。 什么是好算法？Edmonds，1975年提出了一个被沿用至今的标准。,2,Edmonds算法标准,Edmonds算法标准指出具有多项式时间的算法为好 算法。 多项式时间算法：如果是任意一个问题，对存 在着一个算法，它的时间复杂性为O(nk),其中n为输 入规模，k为非负整数，就认为存在着一个解问题 的多项式时间算法。,3,以多项式作为分界函数？,原因有两个： 一、常见算法大致分为两类： 一类是多项式时间内可实现的 另一类需要指数时间（O(cn) 多项式时间算法的可实现性远大于指数

2、时间算法。 （参见P8，表1.2),4,以多项式作为分界函数？,二、多项式时间算法与计算模型无关 算法的研究依赖于计算模型。在不同类型计算模型上实现算法，计算时间不同。 广义ChurchTuring命题：不同计算模型上的计算时间有多项式关系。 多项式与多项式的复合函数是多项式，因此，多项式时间算法与计算模型无关。,5,12.2 P类问题易解的问题,是否每个问题都有多项式时间算法？ 在考虑问题的计算复杂性时，常把它化为相应的判定 问题考虑。 首先看问题分类及其转换。,6,问题分类,一类是判定问题 解只有两种，yes或no。 例：给定图G=(V,E)， 问该图是否有哈密尔顿圈。 一类是优化问题 例

3、：给定图G=(V,E)，假设边的费用为自然数。求该 图的最短哈密尔顿回路。,7,问题转换,优化问题可转换为相应的判定问题求解。 例：给定图G=(V,E)，假设边的费用为自然数。给 定k=1,2,.，问是否有长度不超过k的哈密尔 顿回路。,8,P类问题,P类： 具有多项式时间算法的判定问题形成一个 计算复杂类，记为P类。 P类易解的问题 P-Polynomial 思考：已学知识中哪些问题属P类问题？,9,12.3 NP类问题难解的问题,具有指数时间算法的问题。 例：货郎担问题(TSP问题)。 n!排列方式。 n=6: 6! = 720 n=19: 19! 1.21*1017 每秒排一次，排3.8

4、4*109年 每秒排百万次，排3000年,有算法但实现性差。,10,TSP问题,1998年，解决了美国13509个城市之间的TSP问题 2001年，解决了德国15112个城市之间的TSP问题 解决15112个城市之间的TSP问题，共使用了美国 Rice大学和普林斯顿大学之间网络互连的，由速度为 500MHz 的Compaq EV6 Alpha 处理器组成的110 台计算机，所有计算机花费的时间之和为22.6年。,11,NP类问题,一般而言，验证解比求解易。 对具有指数时间的问题，有些可用不确定性算法求 解。该算法包含两个阶段： 推测阶段 对规模为n的输入实例x，产生一个输出y。 验证阶段 检验

5、y是否满足解形式，是否是解。,12,NP类问题,推测阶段是具有多项式时间的非确定性(non-determinism)算法，对输入实例x,下次产生的输出可能不是y。 验证阶段是具有多项式时间的确定性算法。,13,NP类问题,NP类： 由具有多项式时间的非确定性算法求解的判定问题形成的一个计算复杂类，记为NP类。 NP难解的问题 NPNondeterministic Polynomial,14,NP类问题举例货郎担问题,例：货郎担的判定问题：给定n个城市、正常数k及城 市之间的费用矩阵C，判定是否存在一条经过所有 城市一次且仅一次，最后返回初始出发城市且费用 小于常数k的回路。 算法A用非确定算法

6、在多项式时间内推测一条回路 A用确定算法在多项式时间内判定回路是否是哈密尔顿回路，是否费用和小于k，返回yes或no。,15,NP类问题举例求真因子问题,例：有一个国王向邻国公主求婚。公主出了一道题： 求出48 770 428 433 377 171的一个真因子。若 国王能在一天之内求出答案,公主便接受他的求 婚。 国王，顺序除，一天未算出。 223 092 827 宰相，给全国百姓编号，用自己的编号去除公主给的数，除尽的报数，领赏。,16,国王： 顺序算法 宰相： 并行算法 是否所有的难解问题通过并行计算使其在多项式内可 解？ 关于并行算法：当将一个问题分解到多个处理器上解 决时，由于算法中

7、不可避免地存在必须串行执行的操 作，从而大大地限制了并行计算机系统的加速能力。,NP类问题举例求真因子问题,17,阿达尔定律:串行执行操作仅占全部操作1%，解 题速度最多也只能提高一百倍。,NP类问题举例求真因子问题,阿达尔定理告诉我们，对有些难解问题，即使提高计算机运行速度，也不能在多项式时间内验证。即并非所有的难解问题都属于NP类。,18,非NP问题举例汉诺塔问题,例：汉诺塔问题。 推测阶段给出一种盘子移动方法； 验证阶段需要n步验证该解的正确性。,19,类和NP类问题的差别,主要差别在于： P类问题可以用多项式时间的确定性算法进行判定或求解 NP类问题可以用多项式时间的确定性算法来检查和

8、验证它的解 结论：,20,12.4 NPC问题,NPCNP Complete,NP完全 为定义NP完全问题，首先给出归约的定义。 定义12.1 令和是两个判定问题，如果存在一个 具有如下性能的确定性算法A，可以用多项 式的时间，把问题的实例I转化为问题 的实例I，使得I的答案为yes，当且仅当 I的答案是yes，就称以多项式时间归约 于，记为p。,21,关于归约,根据定义12.1，由于多项式与多项式的复合仍为多 项式，因此可推得： 1）两个判定问题、 若P，且p,则P 2）归约关系p满足传递性：三个判定问题、 、，若p，p，则 p。,22,NP完全问题定义,定义12.2 令是一个判定问题，如果

9、对NP中的每一 个问题NP，有p，就称判定 问题是一个NP难题。 定义12.3 令是一个判定问题，如果： (1) NP； (2) 对NP中的所有问题NP，都有 p； 则称判定问题是NP完全 (NPC)的。,23,P类、NP类、NPC类问题关系,根据定义，可用如下图表示三者之间的关系：,NPC,NP,24,对NPC问题，有个重要性质 对NPC类中的一个问题，如果能够证明用多项式时间的确定性算法来进行求解或判定，那么， NP中的所有问题都可以通过多项式时间的确定性算法来进行求解或判定。,P类、NP类、NPC类问题关系,25,NP完全问题的证明,定理12.1 令和是NP中的两个问题，使得 p。如果是

10、NP完全的，则也是 NP完全的。 根据定理12.1，为证明问题是NP完全的，只需证明 下列两点： (1)NP (2)存在一个NP完全问题，使得p。,26,12.5 几个典型的NPC问题,可满足性问题(SATISFIABILITY) 判定问题：SATISFIABILITY 输入：合取范式(CNF)布尔表达式f 问题：对布尔表达式f中的布尔变量赋值，是否可 使f的真值为真。,27,Cook定理,定理12.2: 可满足性问题SATISFIABILITY是NP完全 的 。(Cook定理，1971年),Stephen Arthur Cook1982年获图灵奖，NP完全性理论的奠基人,Cook定理的意义：

11、给出了第一个NP完全问题，使得对任何问题，只要能证明NP，且SATp，那么是NPC问题。为NPC问题的发现奠定了基础。,28,部分NP完全问题树,以SAT为基础，很快地又证明了很多其他的完全 问题，逐渐形成了一颗以SAT为根的NP完全树。图 12.1给出了这颗树的一小部分，其中每个结点都是 一个NP完全问题，该问题可在多项式时间里，转换 为它的任一儿子结点所表示的问题。,29,部分NP完全问题树,SATISFIABILITY,3-SATISFIABILITY,VERTEX_COVER,CLQUE,SUBSET_SUM,HAM_CYCLE,TRA_SALESMAN,图7.1,30,几个典型的NP

12、C问题,三元可满足性问题(3-SATISFIABILITY),判定问题：3-SATISFIABILITY 输入：三元合取范式f 问题：对布尔表达式f中的布尔变量赋值，是否可 使f的真值为真。,SATISFIABILITYp3-SATISFIABILITY,31,几个典型的NPC问题,图的着色问题(COLORING),判定问题：COLORING 输入：无向图G=(V,E) 问题：是否可用种颜色为图的顶点着色，使 得相邻顶点不会有相同颜色。,3-SATISFIABILITYpCOLORING,32,几个典型的NPC问题,集团问题(CLIQUE),判定问题：CLIQUE 输入：无向图G=(V,E),

13、正整数k 问题：图中是否包含大小为k的集团，即中是 否具有含个顶点的完全子图。,SATISFIABILITYpCLIQUE,33,几个典型的NPC问题,顶点覆盖问题(VERTEX COVER),判定问题：VERTEX COVER 输入：无向图G=(V,E),正整数k 问题：图中是否存在一个大小为k的顶点覆盖,CLIQUE pVERTEX COVER,34,其他的NP完全问题,哈密尔顿回路问题HAMILTONIAN CYCLE,判定问题：HAMILTONIAN CYCLE 输入：无向图G=(V,E) 问题：图中是否存在一条简单回路，使得每个 顶点经过一次且一次。,35,其他的NP完全问题,子集求

14、和问题SUBSET SUM,判定问题：SUBSET SUM 输入：整数集、整数 问题：是否存在的一个子集，使得中整数 之和为。,36,其他的NP完全问题,多处理器调度问题MULTIPROCESSOR SCHEDULING,判定问题：MULTIPROCESSOR SCHEDULING 输入：m个同构处理器、n个作业、时间T 问题：是否可将n个作业分配至m个处理器，使其 在T内完成。,37,NP完全问题的研究现状,已发现3000多个NP完全问题 2000年5月24日，美国克雷数学研究所在巴黎法兰 西学院宣布了七个“千年数学难题”，解决其中一个 可获百万美元奖励。 其中庞加莱猜想已被我国中山大学朱熹平教授和旅 美数学家曹怀东解决。,38,NP完全问题的研究现状,1、NP完全问题 (NP = P?) 2、霍奇猜想 3、庞加莱猜想 4、黎曼假设 5、杨米尔斯理论 6、纳卫尔斯托可方程 7、BSD猜想。,39,解决NP=P?的途径,解决这个猜想，有两种可能： 一种是找到一个这样的算法，只要针对某个特定NP完全问题找到一个多项式算法，即可证明NP = P。 另外一种可能，就是这样的算法是不存在的。