算法设计与分析 王红梅 第二版 第10章 问题的复杂性

第10章问题的复杂性

算法设计与分析—本科生课程DesignandAnalysisofAlgorithm海南大学信息科学技术学院CollegeofInformationScienceandTechnology,HainanUniversity2023/2/4第10章问题的复杂性2计算的限制算法作为求解问题的方法，可以求解现实世界中的很多问题，但有些问题仍然无法用任何算法求解，有些问题虽然有算法可以求解，但需要太长的运行时间或太大的存储空间计算机学科的根本问题是什么能被（有效地）自动计算。图灵：一个问题是可计算的当且仅当它在图灵机上经过有限步骤后得到正确的结果。库克：一个问题是实际可计算的当且仅当它在图灵机上经过多项式步骤后得到正确的结果。易解问题：多项式时间内可解。难解问题：指数时间求解。2023/2/4第10章问题的复杂性3不可解问题UnsolubleProblem难解问题虽没找到多项式时间算法，但按指数时间算法的难解问题至少在理论上可以用计算机求解。但有些问题不论耗多少时间也不能用计算机求解。不能用计算机求解（不论耗费多少时间）的问题称为不可解问题算法的极限2023/2/4第10章问题的复杂性4例：不可解问题典型例子：停机问题（haltingproblem）算法的极限BoolHalt(char*prog,char*input){if(prog对输入input停止执行)returntrue;elsereturnfalse;}VoidContrary(char*prog){do result=Halt(prog,prog);while(result==true);}2023/2/4第10章问题的复杂性5判定问题DecisionProblem判定问题是仅仅要求回答“yes”或“no”的问题。很多实际问题可以转化为一系列更容易研究的判定问题。举例如下：P类问题和NP类问题2023/2/4第10章问题的复杂性6例1：排序问题排序问题的判定形式可叙述为：给定一个整数数组，是否可以按非降序排列例2：图着色问题图着色问题的判定形式可叙述为：给定无向连通图G=（V，E）和一个正整数k，是否可以用k种颜色为G中所有顶点着色，使得任何两个相邻顶点着色不同。例3：TSP问题TSP问题的判定形式可叙述为：P类问题和NP类问题2023/2/4第10章问题的复杂性7给定一个带权图G=（V，E）和一个正整数k，是否有一个经过所有顶点一次且仅一次再回到出发点的回路，其总距离小于k。例4：哈密顿回路问题哈密顿回路问题的判定形式可叙述为：在图G=（V，E）中，是否有一个回路经过所有顶点一次且仅一次再回到出发点。判定问题的重要特性——验证比求易P类问题和NP类问题2023/2/4第10章问题的复杂性8即在计算上对问题求解是困难的，但在计算上判定一个待定解是否解决了该问题却是简单的。例1：求“哈密顿回路问题”是难解问题但验证一个给定顶点序列是不是“哈密顿回路”却很容易，即只需要检查前n个顶点是否互不相同，而最后一个顶点与第一个顶点是否相同例2：求大整数S=49770428644836899的因子是个难问题但要验证a=223092871是不是大整数S的因子却很容易。只要将S除以这个因子，余数为0即可P类问题和NP类问题2023/2/4第10章问题的复杂性9例3：求线性方程组的解可能很困难，但验证一组解是否是方程组的解却很容易，只要将这组解代入方程组中，然后验证是否满足这组方程即可。确定性算法与P类问题定义2.1

设A是求解问题Π的一个算法，如果在算法的整个执行过程中，每一步只有一个确定的选择，则称算法A是确定性（Determinism）算法。P类问题和NP类问题2023/2/4第10章问题的复杂性10定义2.2

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

类（Polynomial）问题。

所有易解问题都是P类问题P类问题和NP类问题非确定性算法与NP类问题

定义2.3

设A是求解问题Π的一个算法，如果算法A以如下猜测并验证的方式工作，就称算法A是非确定性（Nondeterminism）算法：2023/2/4第10章问题的复杂性11猜测阶段在这个阶段，对问题的输入实例产生一个任意字符串y，在算法的每一次运行时，串y的值可能不同，因此，猜测以一种非确定的形式工作。验证阶段

在这个阶段，用一个确定性算法验证：

①检查在猜测阶段产生的串y是否是合适的形式，如果不是，则算法停下来并得到no；②如果串y是合适的形式，则验证它是否是问题的解，如果是，则算法停下来并得到yes，否则算法停下来并得到no。P类问题和NP类问题2023/2/4第10章问题的复杂性12定义2.4

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

P类问题和NP类问题2023/2/4第10章问题的复杂性13P类问题和NP类问题的主要差别：P类问题可以用多项式时间的确定性算法来进行判定或求解；NP类问题可以用多项式时间的非确定性算法来进行判定或求解。

P类问题和NP类问题2023/2/4第3章NP完全理论14NP完全问题的定义

问题背景大量问题都具有下列特性存在多项式时间的非确定性算法，但是不知道是否存在多项式的确定性算法。同时不能证明这些问题中的任何一个不存在多项式时间的确定性算法，这类问题就是NP完全问题。2023/2/4第3章NP完全理论15NP完全问题的定义

定义3.6

令Π是一个判定问题，如果问题Π属于NP类问题，并且对NP类问题中的每一个问题Π'

，都有Π'

∝pΠ，则称判定问题Π是一个NP完全问题（NP

CompleteProblem），可以把NP完全问题记为NPC。

NP类问题NP完全问题问题Π问题Π'

2023/2/4第3章NP完全理论16NPC是NP类问题中最难的一类问题，其中任一个问题至今都没有找到多项式时间算法。NPC问题：NPC有一个特质：如果一个NPC问题能在多项式时间内得到解决，那么NPC中的每个问题都可以在多项式内求解多年的研究表明，目前还没有一NPC问题有多项式时间算法。这些问题也许存在多项式时间算法，但还有待发现；这些问题也许根本就不存在多项式时间算法，但目前缺乏足够的技术来证明这一点。NP完全问题的定义

2023/2/4第3章NP完全理论17P≠NP？P＝NP？

（至今没人证明）

P类问题：是可以用确定性算法在多项式时间内求解的一类问题。

NP类问题：是可以用非确定性算法在多项式时间猜测并验证的一类问题，而且P⊆NP。

目前人们猜测P≠NP，则P类问题、NP类问题、NP完全问题之间的关系如下：

NP类问题P类问题NPC问题NP完全问题的定义

2023/2/4第3章NP完全理论18定义2.7

令Π是一个判定问题，如果对于NP类问题中的每一个问题Π'，都有Π'∝pΠ，则称判定问题Π是一个NP难问题。

NP类问题NP难问题NP完全问题的定义

但问题Π不是NPC问题问题Π'

2023/2/4第3章NP完全理论19

如果Π是NP完全问题，Π’是NP难问题，那么，他们之间的差别在于Π必定是NP类问题，而Π’不一定在NP类问题中。

一般而言，若判定问题属于NP完全问题，则相应的最优化问题属于NP难问题。例1：判定图G=（V，E）中是否存在哈密顿回路是NPC问题而求哈密顿回路中最短路径的TSP问题是NP难问题例2：判定图G=（V，E）中是否存在k个顶点团的问题是NPC问题而求图中顶点数最多的团问题则是NP难问题

NP完全问题和NP难问题的区别：NP完全问题的定义

2023/2/4第3章NP完全理论20证明一个判定问题Π是NP完全问题需要经过两步：

（1）证明问题Π属于NP类问题，也就是说，可以在多项式时间以确定性算法验证一个任意生成的串，以确定它是不是问题的一个解；（2）证明NP类问题中的每一个问题都能在多项式时间变换为问题Π。由于多项式问题变换具有传递性，所以，只需证明一个已知的NP完全问题能够在多项式时间变换为问题Π。

基本的NP完全问题

2023/2/4第3章NP完全理论21NP完全问题的证明思想NP类问题已知的NP完全问题要证明的NP完全问题基本的NP完全问题

问题Π'

2023/2/4第3章NP完全理论221971年，Cook通过Cook定理证明了SAT（合取范式的可满足）问题是NPC问题1972年，Karp证明了十几个问题都是NPC的，以后在此基础上又证明了几千个NPC这些证明思想和技巧的累积极大的丰富了NP完全理论。基本的NP完全问题

2023/2/4第3章NP完全理论23其它NP完全问题：1．三着色问题（3_ColoringProblem）给定无向图G=(V,E)，是否可用三种颜色来为图G着色，使得图中不会有两个邻接顶点具有同一种颜色。

2．独立集问题（INDEPENDENTSETProblem）

给定无向图G=(V,E)，是否存在一个大小为k的独立集S。其中，若其中任意两个顶点都不互相邻接，则称S是图G的独立集。3．划分问题（

PARTITIONProblem）给定一个具有n个整数的集合S，是否能把S划分成两个子集S1和S2，使得S1中的整数之和等于S2中的整数之和。

基本的NP完全问题

2023/2/4第3章NP完全理论244.子集求和问题SUBSETSUM：给定整数集S和整数t，是否存在S的一个子集，使得T中的整数之和为t。5．装箱问题BINPACKING给定大小为S1,S2,…,Sn的物体，箱子的容量为C，以及一个正整数k，是否能够用k个箱子来装这n个物体。7.

多处理器调度问题MultiProcessorSchedulin

给定m个性能相同的处理器、n个作业J1,J2,…,Jn、及每一个作业的运行时间t1,t2,…,tn、以及时间T，是否可以调度这个处理器，使得它们最多在时间T里完成这个作业。基本的NP完全问题

2023/2/4第3章NP完全理论25最大团问题（MaximumCliqueProblem）给定无向图G=（V，E）、正整数k，判定图中是否存在K个顶点，使得它们的导出子图构成完全图。10.哈密顿回路问