算法sNP完全性与近似算法.PPT

算法设计与分析 2017年4月7日 讲授内容：NP完全性与近似算法教　　师：胡学钢、吴共庆 纲要 判定问题与最优化问题 多项式时间归约 利用多项式时间归约分析问题的复杂性 P、NP、NP-hard、NPC 电路可满足性问题 NPC问题的证明方法 顶点覆盖问题 处理NP-hard问题 近似算法 4/7/2017 算法设计与分析-NP完全性与近似算法 2 举例 容易的和困难的问题 最短简单路径vs.最长简单路径问题 欧拉回路vs.汉密尔顿回路 2-SAT问题vs. 3-SAT问题等 4/7/2017 算法设计与分析-NP完全性与近似算法 3 判定问题与最优化问题 最优化问题 问题的每个可行解都对应一个目标函数值，求解这类问题的目的是希望得到一个有最优目标函数值的可行解 判定问题 回答是否存在一个满足问题要求的解，即解只是简单的回答“是(1)”或“否(0)”。 最优化问题与它相应的判定问题具有密切的联系，通过限界最优化问题要优化的目标函数值，通常可以把一个最优化问题转化为一个判定问题。 例如，最短路径问题的目标是找一条从u到v的最短路径，优化的目标函数值是路径的边数。则相应的判定问题(Path)可以描述为：给定一个有向图G，顶点u和v，以及整数k，问图中从u到v是否存在一条最多k条边的路径。 4/7/2017 算法设计与分析-NP完全性与近似算法 4 多项式时间归约 归约(Reduction) 实例: 具体问题的输入 多项式归约算法: 一个过程能转化A的任何一个实例α到B的某个实例β，且过程具有下列性质: （1）该转化过程只需要多项式时间就可以完成； （2）答案是一致的。也就是说，α的答案是“是”当且仅当β的答案也是“是”。 4/7/2017 算法设计与分析-NP完全性与近似算法 5 多项式时间归约 4/7/2017 算法设计与分析-NP完全性与近似算法 6 利用多项式时间归约分析问题的复杂性 用多项式时间归约算法的思想来证明特定的问题B不存在多项式时间算法 假设我们有一个判定问题A，而且我们知道不存在求解A的多项式时间算法。 假设有多项式时间归约算法可以把A的任意一个实例转化为B的一个实例 这样我们可以用简单的反证法来证明B没有多项式时间的算法。 证明的思路是，假设B有多项式时间算法，则按照上述归约算法的思想，我们也能证明A也有多项式时间算法，这与已知不存在求解A的多项式时间算法矛盾。 4/7/2017 算法设计与分析-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} 4/7/2017 算法设计与分析-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 ，则说算法验证了语言。 4/7/2017 算法设计与分析-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。 4/7/2017 算法设计与分析-NP完全性与近似算法 10 P = NP ? /millennium/ Solved???!!!! $1,000,000 offered by Clay Mathematical Institute 4/7/2017 算法设计与分析-NP