NP完全问题(上课)选读

NP完全问题1什么是好算法？算法的种类和数量积累到一定程度时，需要对算法进行比较和分类。什么是好算法？Edmonds，1975年提出了一个被沿用至今的标准。Edmonds算法标准Edmonds算法标准指出具有多项式时间的算法为好算法。多项式时间算法：如果П是任意一个问题，对П存在着一个算法，它的时间复杂性为O(nk),其中n为输入规模，k为非负整数，就认为存在着一个解问题П的多项式时间算法。以多项式作为分界函数？原因有两个：一、常见算法大致分为两类：一类是多项式时间内可实现的另一类需要指数时间（O(cn))多项式时间算法的可实现性远大于指数时间算法。（参见下表)易解问题与难解问题的主要区别在学术界已达成这样的共识：把多项式时间复杂性作为易解问题与难解问题的分界线，主要原因有：1)多项式函数与指数函数的增长率有本质差别问题规模n多项式函数指数函数lognnnlognn2n32nn!1010.01121103.31033.2100100010243628800204.32086.4400800010483762.4E18505.650282.225001250001.0E153.0E641006.6100664.41000010000001.3E309.3E1572)计算机性能的提高对易解问题与难解问题算法的影响假设求解同一个问题有5个算法A1~A5，时间复杂度T(n)如下表，假定计算机C2的速度是计算机C1的10倍。下表给出了在相同时间内不同算法能处理的问题规模情况：T(n)nn′变化n′/n10n100010000n′=10n1020n5005000n′=10n105nlogn2501842nn′10n7.372n270223n3.162n1316n′=n+log10≈n+3≈110103)多项式时间复杂性忽略了系数，不影响易解问题与难解问题的划分问题规模n多项式函数指数函数n8108nn10001.1n20.01n53906255×108510001.6111.035101081091010002.5941.0721001016101010200013780.621000102410111030002.47×10411024观察结论：n≤100时，（不自然的）多项式函数值大于指数函数值，但n充分大时，指数函数仍然超过多项式函数。以多项式作为分界函数？二、多项式时间算法与计算模型无关算法的研究依赖于计算模型。在不同类型计算模型上实现算法，计算时间不同。广义Church—Turing命题：不同计算模型上的计算时间有多项式关系。多项式与多项式的复合函数是多项式，因此，多项式时间算法与计算模型无关。2P类问题—易解的问题是否每个问题都有多项式时间算法？在考虑问题的计算复杂性时，常把它化为相应的判定问题考虑。首先看问题分类及其转换。问题分类一类是判定问题解只有两种，yes或no。例：给定图G=(V,E)，问该图是否有哈密尔顿圈。一类是优化问题例：给定图G=(V,E)，假设边的费用为自然数。求该图的最短哈密尔顿回路。问题转换优化问题可转换为相应的判定问题求解。例：给定图G=(V,E)，假设边的费用为自然数。给定k=1,2,..，问是否有长度不超过k的哈密尔顿回路。P类问题P类：具有多项式时间算法的判定问题形成一个计算复杂类，记为P类。P类—易解的问题P-Polynomial思考：已学知识中哪些问题属P类问题？3NP类问题—难解的问题具有指数时间算法的问题。例：货郎担问题(TSP问题)。n!排列方式。n=6:6!=720n=19:19!≈1.21*1017每秒排一次，排3.84*109年每秒排百万次，排3000年有算法但实现性差。TSP问题1998年，解决了美国13509个城市之间的TSP问题2001年，解决了德国15112个城市之间的TSP问题解决15112个城市之间的TSP问题，共使用了美国Rice大学和普林斯顿大学之间网络互连的，由速度为500MHz的CompaqEV6Alpha处理器组成的110台计算机，所有计算机花费的时间之和为22.6年。NP类问题一般而言，验证解比求解易。对具有指数时间的问题，有些可用不确定性算法求解。该算法包含两个阶段：推测阶段对规模为n的输入实例x，产生一个输出y。验证阶段检验y是否满足解形式，是否是解。NP类问题推测阶段是具有多项式时间的非确定性(non-determinism)算法，对输入实例x,下次产生的输出可能不是y。验证阶段是具有多项式时间的确定性算法。NP类问题NP类：由具有多项式时间的非确定性算法求解的判定问题形成的一个计算复杂类，记为NP类。NP—难解的问题NP—NondeterministicPolynomialNP类问题举例—货郎担问题例：货郎担的判定问题：给定n个城市、正常数k及城市之间的费用矩阵C，判定是否存在一条经过所有城市一次且仅一次，最后返回初始出发城市且费用小于常数k的回路。算法A用非确定算法在多项式时间内推测一条回路A用确定算法在多项式时间内判定回路是否是哈密尔顿回路，是否费用和小于k，返回yes或no。NP类问题举例—求真因子问题例：有一个国王向邻国公主求婚。公主出了一道题：求出48770428433377171的一个真因子。若国王能在一天之内求出答案,公主便接受他的求婚。国王，顺序除，一天未算出。223092827宰相，给全国百姓编号，用自己的编号去除公主给的数，除尽的报数，领赏。国王：顺序算法宰相：并行算法是否所有的难解问题通过并行计算使其在多项式内可解？关于并行算法：当将一个问题分解到多个处理器上解决时，由于算法中不可避免地存在必须串行执行的操作，从而大大地限制了并行计算机系统的加速能力。NP类问题举例—求真因子问题阿达尔定律:串行执行操作仅占全部操作1%，解题速度最多也只能提高一百倍。NP类问题举例—求真因子问题阿达尔定理告诉我们，对有些难解问题，即使提高计算机运行速度，也不能在多项式时间内验证。即并非所有的难解问题都属于NP类。非NP问题举例—汉诺塔问题例：汉诺塔问题。推测阶段给出一种盘子移动方法；验证阶段需要２n步验证该解的正确性。Ｐ类和NP类问题的差别主要差别在于：P类问题可以用多项式时间的确定性算法进行判定或求解NP类问题可以用多项式时间的确定性算法来检查和验证它的解结论：NPPP?NP猜测：4NPC问题NPC—NPComplete,NP完全为定义NP完全问题，首先给出归约的定义。定义1令П和П’是两个判定问题，如果存在一个具有如下性能的确定性算法A，可以用多项式的时间，把问题П’的实例I’转化为问题П的实例I，使得I’的答案为yes，当且仅当I的答案是yes，就称П’以多项式时间归约于П，记为П’∝pП。关于归约根据定义1，由于多项式与多项式的复合仍为多项式，因此可推得：1）两个判定问题П、П’若П∈P，且П’∝pП,则П’∈P2）归约关系∝p满足传递性：三个判定问题П、П′、П″，若П″∝pП′，П′∝pП，则П″∝pП。NP完全问题定义定义2令П是一个判定问题，如果对NP中的每一个问题П′∈NP，有П′∝pП，就称判定问题П是一个NP难题。定义3令П是一个判定问题，如果：(1)П∈NP；(2)对NP中的所有问题П′∈NP，都有П′∝pП；则称判定问题П是NP完全(NPC)的。P类、NP类、NPC类问题关系根据定义，可用如下图表示三者之间的关系：ＰNPCNP对NPC问题，有个重要性质对NPC类中的一个问题，如果能够证明用多项式时间的确定性算法来进行求解或判定，那么，NP中的所有问题都可以通过多项式时间的确定性算法来进行求解或判定。P类、NP类、NPC类问题关系NP完全问题的证明定理1令П和П′是NP中的两个问题，使得П′∝pП。如果П′是NP完全的，则П也是NP完全的。根据定理1，为证明问题П是NP完全的，只需证明下列两点：(1)П∈NP(2)存在一个NP完全问题П′，使得П′∝pП。5几个典型的NPC问题可满足性问题(SATISFIABILITY)判定问题：SATISFIABILITY输入：合取范式(CNF)布尔表达式f问题：对布尔表达式f中的布尔变量赋值，是否可使f的真值为真。)()()(4325431532xxxxxxxxxxf例：Cook定理定理2:可满足性问题SATISFIABILITY是NP完全的。(Cook定理，1971年)StephenArthurCook—1982年获图灵奖，NP完全性理论的奠基人Cook定理的意义：给出了第一个NP完全问题，使得对任何问题П，只要能证明П∈NP，且SAT∝pП，那么П是NPC问题。为NPC问题的发现奠定了基础。部分NP完全问题树以SAT为基础，很快地又证明了很多其他的ＮＰ完全问题，逐渐形成了一颗以SAT为根的NP完全树。图1给出了这颗树的一小部分，其中每个结点都是一个NP完全问题，该问题可在多项式时间里，转换为它的任一儿子结点所表示的问题。部分NP完全问题树SATISFIABILITY3-SATISFIABILITYVERTEX_COVERCLＩQUESUBSET_SUMHAM_CYCLETRA_SALESMAN1几个典型的NPC问题三元可满足性问题(3-SATISFIABILITY)判定问题：3-SATISFIABILITY输入：三元合取范式f问题：对布尔表达式f中的布尔变量赋值，是否可使f的真值为真。SATISFIABILITY∝p3-SATISFIABILITY几个典型的NPC问题图的着色问题(COLORING)判定问题：COLORING输入：无向图G=(V,E)问题：是否可用ｋ种颜色为图Ｇ的顶点着色，使得相邻顶点不会有相同颜色。3-SATISFIABILITY∝pCOLORING几个典型的NPC问题集团问题(CLIQUE)判定问题：CLIQUE输入：无向图G=(V,E),正整数k问题：图Ｇ中是否包含大小为k的集团，即Ｇ中是否具有含ｋ个顶点的完全子图。SATISFIABILITY∝pCLIQUE几个典型的NPC问题顶点覆盖问题(VERTEXCOVER)判定问题：VERTEXCOVER输入：无向图G=(V,E),正整数k问题：图Ｇ中是否存在一个大小为k的顶点覆盖CLIQUE∝pVERTEXCOVER的顶点覆盖。的一个大小为图为则称或，都有任意的，使得对，顶点覆盖定义：若存在kGV,Vu),(kVVVVvEvu其他的NP完全问题哈密尔顿回路问题HAMILTONIANCYCLE判定问题：HAMILTONIANCYCLE输入：无向图G=(V,E)问题：图Ｇ中是否存在一条简单回路，使得每个顶点经过一次且一次。其他的NP完全问题子集求和问题SUBSETSUM判定问题：SUBSETSUM输入：整数集Ｓ、整数ｔ问题：是否存在Ｓ的一个子集Ｔ，使得Ｔ中整数之和为ｔ。其他的NP完全问题多处理器调度问题MULTIPROCESSORSCHEDULING判定问题：MULTIPROCESSORSCHEDULING输入：m个同构处理器、n个作业、时间T问题：是否可将n个作业分配至m个处理器，使其在T内完成。NP完全问题的研究现状已发现3000多个NP完全问题2000年5月24日，美国克雷数学研究所在巴黎法兰西学院宣布了七个“千年数学难题”，解决其中一个可获百万美元奖励。其中庞加莱猜想已被我国中山大学朱熹平教授和旅美数学家曹怀东解决。NP完全问题的研究现状1、NP完全问题(NP=P?)2、霍奇猜想3、庞加莱猜想4、黎曼假设5、杨－米尔斯理论6、纳卫尔－斯托可方程7、BSD猜想。解决NP=P?的途径解决这个猜想，有两种可能：一种是找到一个这样的算法，只要针对某个特定NP完全问题找到一个多项式算法，即可证明NP=P。另外一种可能，就是这样的算法是不