NP完全问题(上课)选读

NP类问题
NP类： 由具有多项式时间的非确定性算法求解的判 定问题形成的一个计算复杂类，记为NP类。
NP—难解的问题 NP—Nondeterministic Polynomial
NP类问题举例—货郎担问题
例：货郎担的判定问题：给定n个城市、正常数k及城 市之间的费用矩阵C，判定是否存在一条经过所有 城市一次且仅一次，最后返回初始出发城市且费用 小于常数k的回路。
NP完全问题
1 什么是好算法？
算法的种类和数量积累到一定程度时，需要对 算法进行比较和分类。 什么是好算法？Edmonds，1975年提出了一个被 沿用至今的标准。
Edmonds算法标准
Edmonds算法标准指出具有多项式时间的算法为好 算法。 多项式时间算法：如果П 是任意一个问题，对П 存 在着一个算法，它的时间复杂性为O(nk),其中n为输 入规模，k为非负整数，就认为存在着一个解问题П 的多项式时间算法。
算法A用非确定算法在多项式时间内推测一条回路 A用确定算法在多项式时间内判定回路是否是哈密 尔顿回路，是否费用和小于k，返回yes或no。

NP类问题举例—求真因子问题
例：有一个国王向邻国公主求婚。公主出了一道题： 求出48 770 428 433 377 171的一个真因子。若 国王能在一天之内求出答案,公主便接受他的求 婚。 国王，顺序除，一天未算出。 223 092 827 宰相，给全国百姓编号，用自己的编号去除公主 给的数，除尽的报数，领赏。
T(n) 10n 20n 5nlogn 2n2 2n n 1000 500 250 70 13 n′ 10000 5000 1842 223 16
10
变化 n′=10n n′=10n 10 n<n′<10n n n′=n+log10≈n+3
n′/n 10 10 7.37 3.16 ≈1
3) 多项式时间复杂性忽略了系数，不影响易解问题与难 解问题的划分
问题转换
优化问题可转换为相应的判定问题求解。
例：给定图G=(V,E)，假设边的费用为自然数。给 定k=1,2,..，问是否有长度不超过k的哈密尔 顿回路。
P类问题
P类： 具有多项式时间算法的判定问题形成一个 计算复杂类，记为P类。
P类—易解的问题 P-Polynomial 思考：已学知识中哪些问题属P类问题？
Hale Waihona Puke NP类问题一般而言，验证解比求解易。 对具有指数时间的问题，有些可用不确定性算法求 解。该算法包含两个阶段：
推测阶段 对规模为n的输入实例x，产生一个输出y。

验证阶段 检验y是否满足解形式，是否是解。

NP类问题
推测阶段是具有多项式时间的非确定性(nondeterminism)算法，对输入实例x,下次产生的输出 可能不是y。 验证阶段是具有多项式时间的确定性算法。
多项式函数 问题规模 2 nlog logn n n n n
1
10 20 50
n3
1
1000 8000 125000
指数函数 2n n!
2
1024 1048376 1.0E15
0
3.3 4.3 5.6
1
10 20 50
0.0
33.2 86.4 282.2
1
100 400 2500
1
3628800 2.4E18 3.0E64

NP类问题举例—求真因子问题
国王： 顺序算法 宰相： 并行算法
3 NP类问题—难解的问题
具有指数时间算法的问题。
例：货郎担问题(TSP问题)。
n!排列方式。 n=6: 6! = 720 n=19: 19! ≈ 1.21*1017 每秒排一次，排3.84*109年 每秒排百万次，排3000年
有算法但实现性差。
TSP问题
1998年，解决了美国13509个城市之间的TSP问题 2001年，解决了德国15112个城市之间的TSP问题 解决15112个城市之间的TSP问题，共使用了美国 Rice大学和普林斯顿大学之间网络互连的，由速度为 500MHz 的Compaq EV6 Alpha 处理器组成的110 台计算机，所有计算机花费的时间之和为22.6年。
问题规模n
5 10 100 1000 多项式函数 n8 390625 108 1016 1024 108n 5×108 109 1010 1011 n1000 51000 101000 102000 103000 1.1n 1.611 2.594 13780.6 指数函数 20.01n 1.035 1.072 2
100
6.6
100
664.4
10000
1000000
1.3E30
9.3E157
2) 计算机性能的提高对易解问题与难解问题算法 的影响
假设求解同一个问题有5个算法A1~A5，时间复杂 度T(n)如下表，假定计算机C2的速度是计算机C1 的10倍。下表给出了在相同时间内不同算法能处理 的问题规模情况：
2 P类问题—易解的问题
是否每个问题都有多项式时间算法？
在考虑问题的计算复杂性时，常把它化为相应的判定 问题考虑。 首先看问题分类及其转换。
问题分类

一类是判定问题
解只有两种，yes或no。 例：给定图G=(V,E)， 问该图是否有哈密尔顿圈。

一类是优化问题 例：给定图G=(V,E)，假设边的费用为自然数。求该 图的最短哈密尔顿回路。
2.47×1041 1024
观察结论：n≤100时，（不自然的）多项式函数值大于指数 函数值，但n充分大时，指数函数仍然超过多项式函数。
以多项式作为分界函数？
二、多项式时间算法与计算模型无关 算法的研究依赖于计算模型。在不同类型计算模型 上实现算法，计算时间不同。
广义Church—Turing命题：不同计算模型上的计算 时间有多项式关系。 多项式与多项式的复合函数是多项式，因此，多项 式时间算法与计算模型无关。
以多项式作为分界函数？
原因有两个： 一、常见算法大致分为两类： 一类是多项式时间内可实现的 另一类需要指数时间（O(cn))
多项式时间算法的可实现性远大于指数时间算法。 （参见 下表 )
易解问题与难解问题的主要区别
在学术界已达成这样的共识：把多项式时间复杂性作 为易解问题与难解问题的分界线，主要原因有： 1) 多项式函数与指数函数的增长率有本质差别