第10章_问题的复杂性分析

计算的限制
算法作为求解问题的方法，可以求解现实世界中的很 多问题，但有些问题仍然无法用任何算法求解，有些 问题虽然有算法可以求解，但需要太长的运行时间或 太大的存储空间 计算机学科的根本问题是什么能被（有效地）自动计 算。图灵：一个问题是可计算的当且仅当它在图灵机 上经过有限步骤后得到正确的结果。库克：一个问题 是实际可计算的当且仅当它在图灵机上经过多项式步 骤后得到正确的结果。易解问题：多项式时间内可解。 难解问题：指数时间求解。
定义2.4 如果对于某个判定问题Π ，存在一个非负整数k，对 于输入规模为n的实例，能够以O( nk )的时间运行一个非确定 性算法，得到yes或no的答案，则该判定问题Π 是一个 NP 类 （Nondeterministic Polynomial）问题。
2018/10/14
第10章 问题的复杂性
12

2018/10/14
第10章 问题的复杂性
3
算法的极限

例：不可解问题典型例子：停机问题（halting problem）
Bool Halt(char *prog, char *input){ if(prog对输入input停止执行) return true; else return false; } Void Contrary(char *prog){ do result=Halt(prog, prog); while(result==true); }

2018/10/14
第10章 问题的复杂性
6
P类问题和NP类问题
给定一个带权图G=（V，E）和一个正整数k，是 否有一个经过所有顶点一次且仅一次再回到出发 点的回路，其总距离小于k。 例4：哈密顿回路问题 哈密顿回路问题的判定形式可叙述为： 在图G=（V，E）中，是否有一个回路经过所有 顶点一次且仅一次再回到出发点。 判定问题的重要特性——验证比求易
在多项式的确定性算法。
同时不能证明这些问题中的任何一个不存在多项式时
间的确定性算法，这类问题就是NP完全问题。
2018/10/14
第3章 NP完全理论
14
问题变换
定义 10.5 假设问题Π’存在一个算法A，对于问题Π’的 输入实例I’，算法A求解问题Π’得到一个输出O’，另外一个 问题Π的输入实例是I，对应于输入I，问题Π有一个输出O， 则从问题Π问题Π’是一个三步的变换过程： 1. 输入转换：把问题 Π的输入 I 转换为问题 Π‘ 的适当输入 I’ ； 2. 问题求解：对问题Π‘应用算法A产生一个输出O ’； 3. 输出转换：把问题 Π '的输出O'转换为问题Π 对应于输入 I的正确输出。
配对问题排序问题的变换有助于建立配对问题代价的一 个上限，因为上述输入和输出转换都是在多项式时间完成， 所以，如果排序问题有多项式时间算法，则配对问题也一定 有多项式时间算法。
2018/10/14 第10章 问题的复杂性 19
问题变换

注：问题变换的主要目的不是给出解决 一个问题的算法，而是给出通过另一个 问题理解一个问题的计算时间上下限的 一种方式。
P类问题和NP类问题

P类问题和NP类问题的主要差别：



P类问题可以用多项式时间的确定性算法来进行判定或求解； NP类问题可以用多项式时间的非确定性算法来进行判定或 求解。 如果问题Π属于P类，则存在一个多项式时间的确定性算法 来判定和求解，显然，也可以构造一个多项式时间的非确定 性算法来验证其解的正确性，因些问题Π也属于NP类，即
第10章 问题的复杂性
24
NP完全问题的定义
NP完全问题和NP难问题的区别：
NP完全问题必定是NP类问题，NP难问题不一定是 NP类问题中。 一般而言，若判定问题属于NP完全问题，则相应 的最优化问题属于NP难问题。
例1：判定图G=（V，E）中是否存在哈密顿回路是NPC问题 而求哈密顿回路中最短路径的TSP问题是NP难问题
2018/10/14
第10章 问题的复杂性
20
NP完全问题的定义
定义10.6 令Π 是一个判定问题，如果问题Π 属于NP类问题， 并且对NP类问题中的每一个问题Π' ，都有Π' ∝pΠ ，则称判定 问题Π 是一个NP完全问题（NP Complete Problem），可以 把NP完全问题记为NPC。
2018/10/14
第10章 问题的复杂性
15
问题变换
问题变换的一般过程
问题Π 问题Π' I'
算法A
I
输入转换
O'
输出转换
O
2018/10/14
第10章 问题的复杂性
16
问题变换

问题变换意义

若在 O( (n)) 的时间内完成上述输入和输出转换，则 称问题 以 (n) 时间变换到问题 ' ，记为：

非确定性算法与NP类问题
如下猜测并验证的方式工作，就称算法 A 是非确定性 （Nondeterminism）算法：
定义2.3 设A是求解问题Π的一个算法，如果算法A以
2018/10/14
第10章 问题的复杂性
10
P类问题和NP类问题

猜测阶段
在这个阶段，对问题的输入实例产生一个任意字符串 y， 在算法的每一次运行时，串y的值可能不同，因此，猜 测以一种非确定的形式工作。

2018/10/14
第10章 问题的复杂性
22
NP完全问题的定义
P≠NP？P＝NP？ （至今没人证明）
P类问题：是可以用确定性算法在多项式时间内求解的一 类问题。 NP类问题：是可以用非确定性算法在多项式时间猜测并 验证的一类问题，而且P⊆NP。
目前人们猜测P≠NP，则P类问题、NP类问题、NP完全问题 之间的关系如下：
问题Π'
NP类问题
NP完全问题
问题Π
2018/10/14
第10章 问题的复杂性
21
NP完全问题的定义


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

2018/10/14
第10章 问题的复杂性
7
P类问题和NP类问题

即在计算上对问题求解是困难的，但在计算上判定一个 待定解是否解决了该问题却是简单的。 例1：求“哈密顿回路问题”是难解问题 但验证一个给定顶点序列是不是“哈密顿回路”却很 容易，即只需要检查前n个顶点是否互不相同，而最 后一个顶点与第一个顶点是否相同 例2：求大整数S=49 770 428 644 836 899的因子 是个难问题 但要验证a=223 092 871是不是大整数S的因子却很 容易。只要将S除以这个因子，余数为0即可
2018/10/14 第10章 问题的复杂性 4
P类问题和NP类问题

判定问题 Decision Problem


判定问题是仅仅要求回答“yes”或“no”的问题。
很多实际问题可以转化为一系列更容易研究的 判定问题。举例如下：
2018/10/14
第10章 问题的复杂性
5
P类问题和NP类问题
例1：排序问题 排序问题的判定形式可叙述为： 给定一个整数数组，是否可以按非降序排列 例2：图着色问题 图着色问题的判定形式可叙述为： 给定无向连通图G=（V，E）和一个正整数k，是 否可以用k种颜色为G中所有顶点着色，使得任何 两个相邻顶点着色不同。 例3：TSP问题 TSP问题的判定形式可叙述为：
( n) '
其中，n为问题规模； 若在多项式时间内完成上述输入和输出转换，则称 问题 以多项式时间变换到问题 ' ，记为：
p '
2018/10/14
第10章 问题的复杂性
17
问题变换
例：配对问题排序的问题变换
排序问题——输入I'是一组整数X=(x1, x2, …, xn)， 输出O'是这组整数的一个排列xi1≤xi2≤…≤xin。 配对问题——输入I是两组整数X=(x1, x2, …, xn)和 Y=(y1, y2, …, yn)，输出O是两组整数的元素配对， 即X中的最小值与Y中的最小值配对，X中的次小 值与Y中的次小值配对，依此类推。
2018/10/14
第10章 问题的复杂性
9
P类问题和NP类问题
定义2.2
如果对于某个判定问题Π ，存在一个非负整数k， 对于输入规模为n的实例，能够以O(nk) 的时间运行一个确 定性算法，得到yes或no的答案，则该判定问题Π 是一个 P 类（Polynomial）问题。
所有易解问题都是P类问题
2018/10/14
第10章 问题的复杂性
18
问题变换
配对问题排序问题的变换过程
假设存在算法A解决排序问题，则配对问题可以变换到排序问题： 1．把配对问题的输入I转化为排序问题的两个输入I1'和I2'； 2 ．排序这两组整数，即应用算法 A 对两个输入 I1' 和 I2' 分别排序得 到两个有序序列O1 '和O2 '； 3．把排序问题的输出 O1'和O2' 转化为配对问题的输出 O，这可以 通过配对每组整数的第一个元素、第二个元素、……来得到。
NP类问题 NPC问题 P类问题
2018/10/14