算法2013s-np完全性与近似算法.pptx

算法设计与分析
2018年2月12日
讲授内容:NP完全性与近似算法教师:胡学钢、吴共庆
纲要
判定问题与最优化问题
多项式时间归约
利用多项式时间归约分析问题的复杂性
P、NP、NP-hard、NPC
电路可满足性问题
NPC问题的证明方法
顶点覆盖问题
处理NP-hard问题
近似算法
2/12/2018
算法设计与分析-NP完全性与近似算法
2
举例
容易的和困难的问题


2-SAT问题vs. 3-SAT问题等
2/12/2018
算法设计与分析-NP完全性与近似算法
3
判定问题与最优化问题
最优化问题
问题的每个可行解都对应一个目标函数值,求解这类问题的目的是希望得到一个有最优目标函数值的可行解
判定问题
回答是否存在一个满足问题要求的解,即解只是简单的回答“是(1)”或“否(0)”。
最优化问题与它相应的判定问题具有密切的联系,通过限界最优化问题要优化的目标函数值,通常可以把一个最优化问题转化为一个判定问题。
例如,最短路径问题的目标是找一条从u到v的最短路径,优化的目标函数值是路径的边数。则相应的判定问题(Path)可以描述为:给定一个有向图G,顶点u和v,以及整数k,问图中从u到v是否存在一条最多k条边的路径。
2/12/2018
算法设计与分析-NP完全性与近似算法
4
多项式时间归约
归约(Reduction)
实例: 具体问题的输入
多项式归约算法:
一个过程能转化A的任何一个实例α到B的某个实例β,且过程具有下列性质:
(1)该转化过程只需要多项式时间就可以完成;
(2)答案是一致的。也就是说,α的答案是“是”当且仅当β的答案也是“是”。
2/12/2018
算法设计与分析-NP完全性与近似算法
5
多项式时间归约
2/12/2018
算法设计与分析-NP完全性与近似算法
6
利用多项式时间归约分析问题的复杂性
用多项式时间归约算法的思想来证明特定的问题B不存在多项式时间算法
假设我们有一个判定问题A,而且我们知道不存在求解A的多项式时间算法。
假设有多项式时间归约算法可以把A的任意一个实例转化为B的一个实例
这样我们可以用简单的反证法来证明B没有多项式时间的算法。
证明的思路是,假设B有多项式时间算法,则按照上述归约算法的思想,我们也能证明A也有多项式时间算法,这与已知不存在求解A的多项式时间算法矛盾。
2/12/2018
算法设计与分析-NP完全性与近似算法
7
P、NP、NP-hard、NPC
一个具体问题是多项式时间可解的
如果该问题存在一个多项式时间O(nk)求解算法,其中k为一个常数。因此我们可以定义复杂类P为多项式时间可解的具体判定问题的集合。
定义 P类语言= {L∈{0, 1}* : there exists an algorithm A that decides L in polynomial time}
定理P类语言={L : L is accepted by a polynomial-time algorithm}
2/12/2018
算法设计与分析-NP完全性与近似算法
8
P、NP、NP-hard、NPC
定义验证算法A为带两个参数的算法。一个参数是给定的输入串x(即输入实例),另一个参数是一个证书y(即解)。如果存在一个证书y,使得A(x,y) = 1 ,则说算法A验证了输入串x。因此,我们可以定义能够被算法A所验证的语言
L={x∈{0,1}*:there exists y∈{0,1}* such that A(x, y)=1}.
直观地说,如果对任何的串x,存在证书y,能够用该证书证明x ∈ L,而且,对任何x ∉ L,没有证书能够证明x∈L ,则说算法验证了语言。
2/12/2018
算法设计与分析-NP完全性与近似算法
9
P、NP、NP-hard、NPC
复杂类NP
定义复杂类NP指的是一类能够被多项式时间验证算法所验证语言的集合。
一个语言L属于NP当且仅当存在有两个输入的多项式时间算法A和常数c,使得
L = {x∈{0, 1}* : there exists a certificate y with |y| = O(|x|c) such that A(x, y) = 1}.
意思是说,算法A在多项式时间内验证了语言L。
2/12/2018
算法设计与分析-NP完全性与近似算法
10