第1页:第十章 NP难度和NP完全问题章节封面
1第十章NP难度和NP完全问题
第2页:本章目录
210.1基本概念10.1.1不确定算法10.1.2 NP难度和NP完全类
第3页:预备知识:复杂度回顾
3预备知识
- 算法时间复杂度的渐进表示上界O,下界Ω
- 多项式时间算法与非多项式时间算法检索:O(logn)排序:O(nlogn)货郎担问题:O(n22n)背包问题:O(2n/2)算法的时间复杂度一旦大于多项式时间,算法的执行时间会随n的增大而急剧增加。即使中等规模的问题也解不出。O(1) <O(logn) <O(n) <O(nlogn) <O(n2) <O(n3)O(2n) <O(n!) <O(nn)10.1基本概念
第4页:问题复杂性与算法复杂性的区别
4问题复杂性和算法复杂性的区别
- 算法的复杂性是指解决问题的一个具体的算法的执行时间,这是算法的性质;
- 问题的复杂性是指这个问题本身的复杂程度,是问题的性质。例:排序问题,如果只能通过元素间的相互比较来确定元素间的相互位置,而没有其他的附加可用信息,则排序问题的复杂性是O(nlgn)但是排序算法很多,冒泡法是O(n2),快速排序平均情况下是O(nlgn)等等,排序问题的复杂性是指在所有的解决该问题的算法中最好算法的复杂性。问题的复杂性不可能通过枚举各种可能算法来得到,一般都是预先估计一个值,然后从理论上证明。
第5页:确定算法与不确定算法
5确定算法
- 运算结果是唯一确定的,对于同样的输入,它的输出从不改变。
- 之前介绍的算法都是确定算法
- 确定算法可以在确定型图灵机上执行不确定算法
- 运算结果不是唯一确定的
- 不确定算法可以在非确定型图灵机上执行10.1.1不确定的算法
第6页:图灵机
6图灵机
- 1936年图灵提出了一个抽象计算模型──图灵机,并用它来精确定义可计算函数。图灵机的基本思想是模拟人用纸笔进行数学运算的过程,这个运算过程可分解为下面两种简单的动作:1.在纸上写或擦除某个符号;2.把注意力从纸的一个位置移动到另一个位置。
- 在每个阶段将由执行运算的人决定下一步的动作,而他的决定依赖于此人当前所关注的是纸上哪个位置的符号,以及此人当前思维的状态。
第7页:图灵机模型示意
7Turing Machine
第8页:不确定算法的两个阶段
810.1.1不确定的算法
- 不确定的算法由两个阶段组成
- 猜测阶段:产生一个任意字符串C,可以看成是问题实例的解的猜测,可能在不确定性算法的不同次运行中不同.
- 验证阶段:是一个确定的可执行子程序.检查字符串C是否是问题实例的解,若是,算法终止且输出YES,否则输出NO.两阶段都能在多项式时间内完成
第9页:不确定算法的三个语句
- 9函数:choice(S):任意选取集合S中的一个元素例:choice(1:n)选择区域[1,n]中任一整数语句:failure:发出不成功完成的信号当且仅当所有的选择都不会导致成功时,算法以不成功stopsuccess:发出成功完成的信号每当有一组选择导致成功时,算法以成功stop
- failure和success相当于stop语句,无return的作用
- choice,failure和success的计算时间均为O(1)在SPARKS语言中一个函数和两个语句
第10页:不确定机上的检索问题
10不确定算法举例-不确定机上的检索问题考察给定元素集A(1:n),n≥1,检索元素x是否在A中。生成一个随机整数j,1≤j≤n;判断A(j)和x是否相等。j←choice(1:n) if A(j)=x then print(j);success endif print(‘0’);failure随机产生一个数,不确定的复杂度O(1)确定的检索算法的复杂度为Ω(n).
第11页:不确定机上的分类问题
11不确定算法举例-不确定机上的分类问题 设A(i)是一个待分类的正整数集,设计不确定算法按照非降次序分类并输出。 辅助数组B,初始化为0 逐个将A中的元素,放入B(j),j为“猜测”出的正整数, 检查B中元素是否按非降次序排列。 procedure NSORT(A,n) integer A(n), B(n), n,i,jB←0 for i←1 to n doj←choice(1:n)ifB(j)≠0 thenfailure endifB(j)←A(i) repeat for i←1 to n-1 do if B(i)>B(i+1) thenfailure endif repeat print(B)success end NSORT若B(j)已被占用,失败若存在降序,失败时间复杂度:O(n)确定分类算法:Ω(nlogn)
第12页:不确定机的理论模型性质
12不确定机在现实技术条件下是不存在的,是为了分析计算机复杂度难题而虚构的理论模型。
可以设想不确定机在执行choice(S)语句时,具有主动选择正确值(导致success)的能力,这是通过同时复制大量副本并行实现的。
不确定算法的设计思路一般是,先随机生成解,再检查是否为答案。
不确定算法的执行
第13页:不确定判定算法的输出
13只关心唯一输出的不确定算法不确定的判定算法只产生0/1输出:只需要回答yes或者no的问题。
0:当且仅当没有一种选择可导致success1:当且仅当至少存在一种选择导致success输出隐含于success和failure,此外无输出语句不确定的判定算法
第14页:判定问题的意义
14判定问题许多最优化问题都可以转化为判定问题。
很多问题满足性质:判定问题在多项式时间内求解当且仅当对应的最优化问题可以在多项式时间内求解,反之亦然。
如果判定问题不能在多项式时间内求解,那么与它相应的最优化问题也不能在多项式时间内求解。
第15页:图着色问题的判定形式
15优化问题表示为判定问题形式
- 图着色问题:已知n点图G=<V,E>,求对G的n个顶点进行着色的一种方法(相邻顶点颜色不同),使得所用颜色的总数最小。已知n点图G=<V,E>,问图G是否可用k种颜色进行着色?
- 优化的结果包含了判定的结果,但判定的结果并不包含优化结果。
- 从判定解不难得到它的最优解。GCD(G,n)⇒GCD(G,n,k) k=2,3…,n
第16页:最大集团问题的判定形式
16优化问题表示为判定问题形式-最大集团
- 最大集团G的一个集团(clique):图G=<V,E>的最大完全子图。集团的大小用所含的结点数来量度。最大集团问题:确定G内最大集团的大小问题。对应判定问题:对于某个给定的k,确定G是否有一个大小至少为k的集团。
第17页:DCLIQUE与最大集团求解
17优化问题表示为判定问题形式-最大集团
- DCLIQUE(G,k)为集团判定问题的一个确定判定算法:1.设|V|=n,G内的最大集团的大小可多次应用DCLIQUE(G,k)而求得。2.对于k=n, n−1, n−2,…直到DCLIQUE(G,k)输出为1为止。
- 如果DCLIQUE的时间复杂度为f(n),则最大集团的大小可在n×f(n)时间内求出。
- 如果最大集团的大小可以在g(n)时间内确定,则其判定问题也可在g(n)时间内求出。
第18页:0/1背包问题的判定形式
18优化问题表示为判定问题形式-0/1背包问题0/1背包的判定问题:对于给定的非负数R,pi和wi,1≤i ≤n,确定是否存在一组xi的0/1赋值,使得Σpixi≥R且Σwixi≤M如果0/1背包的判定问题不能在多项式时间内求解,那么与它相应的最优化问题也不能在多项式时间内求解。
第19页:不确定算法的时间复杂度
19不确定算法的时间复杂度
- 定义10.1一个不确定算法所需的时间是指当存在一选择序列导致一成功完成时,为了完成任意给定的一个输入而达到成功完成所需步骤的最小值;在不成功完成的情况下所需的时间是O(1).假如对于所有的大小为n(n≥n0)的输入,导致成功完成需要的时间至多为c×f(n),其中c和n0是两个常数,则这个不确定算法的复杂度为O(f(n)).
第20页:最大集团判定的不确定算法
20最大集团判定问题的不确定算法 procedure DCK(G,n,k)S←∅ for i←1 to k dot←choice(1:n) if t∈S thenfailure endifS←S∪t repeatfor使得i∈S, j∈S的每一对(i,j),and i≠jdo if (i,j)不是此图的边 thenfailure endif repeatsuccess end DCKS是“猜测”的k个顶点的集合,初值为空集若t是一个已生成过的顶点,失败k个顶点之间都有边连接O(n+k2)=O(n2)=O(m)m为输入长度k个不同结点集合
第21页:可满足性问题与合取范式
21可满足性问题-概念
- 令x1,x2,…xn表示布尔变量(它们的值既可为真也可为假)。命题公式由布尔变量、布尔常量以及布尔运算符组成。合取范式(CNF):形如A1∧A2∧…∧Am;其中:Ai为子句,析取范式(DNF):形如B1∨B2∨…∨Bn,Bi是短语
第22页:命题公式的归纳定义
22原子:命题的抽象,用大写的英文字母P,Q,…等表示。
公式:是如下定义的一个符号串:(1)原子是公式;
(2)F、T是公式;
(3)若G,H是公式,则(~G),(G∨H),(G∧H),(G→H),(G↔H)是公式;
(4)所有公式都是有限次使用(1),(2),(3)得到的符号串。
可满足性问题:对于变量的任意一组真值指派,确定公式是否为真。
CNF可满足性:对于CNF公式的可满足性问题。
可满足性问题-概念
第23页:SAT问题的地位
- 23可满足性(SAT)问题SAT问题来源于许多实际的逻辑推理类的应用问题。是建立NP完全理论的突破点。对于一个多项式时间的不确定算法,当且仅当给定的命题公式E(x1,x2,…,xn)是可满足的。则算法成功终止。
- 可满足性问题的不确定算法思想:从2n组可能的真值指派中不确定地选取一组赋给(x1,x2,…,xn)验证其对给定的命题公式E(x1,x2,…,xn)是否为真。
第24页:EVAL过程
24 procedure EVAL(E,n) boolean x(n) for i←1 to n doxi←choice(true,false) repeat if E(x1,x2,…xn)=true thensuccess elsefailure endif end EVAL对n个变量赋予一组真值指派不确定时间为O(n)
第25页:判定问题研究的意义
25说明
- 为了研究问题的复杂性,必须将问题抽象,为了简化问题,我们只考虑一类简单的问题,判定性问题。
- 任何一般的最优化问题都可以转化为一系列判定性问题;
- 如果一个判定性问题的复杂度是该问题的一个实例规模n的多项式函数,则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题集合。
第26页:P类与NP类的定义
2610.1.2 NP难度和NP完全类
- 定义10.2:P是所有可在多项式时间内用确定算法求解的判定问题的集合。NP是所有可在多项式时间内用不确定算法求解的判定问题的集合。
- 存在不是NP问题的问题:猜到一个解,但不能在多项式时间内验证它。
- P⊆NP(所有P类问题都是NP问题,确定算法是不确定算法的特例)
- 注:NP问题不一定都是难解的问题,比如:简单的数组排序问题是P类问题,但P属于NP,也是NP问题
- Note:NP问题不是非P类问题
- P=NP?P≠NP?由此研究产生了cook定理NP问题是指可以用不确定算法在多项式时间里验证一个解的问题另一个定义:可以用不确定算法在多项式时间里猜出一个解的问题
第27页:Cook定理
27cook定理
- 【cook定理】可满足性(SAT)在P内,当且仅当P=NP。SAT问题如果有多项式解,当且仅当P=NP
第28页:约化的定义
- 2810.1.2 NP难度和NP完全类定义10.3(约化):令L1和L2是两个问题,如果有一确定的多项式时间算法求解L1,而这个算法使用了一个在多项式时间内求解L2的确定算法,则称L1约化为L2(L1∝L2)
- 问题L1约化为问题L2的含义是:可以用问题L2的解法解决问题L1,或者说,问题L1可以“变成”问题L2
- 判定问题L1到判定问题L2的归约:存在一个转换函数F,可以把问题L1的输入x转换为问题L2的输入F(x),满足:问题L1对于输入x得到正确结果当且仅当问题L2对于输入F(x)得到正确结果。问题L1的算法FL2的算法F(X)L2的输入XL1的输入Yes or No问题L1和L2的结果
第29页:约化举例
29约化举例
- 判定问题L1:判定n个布尔值中是否至少有一个为true.
- L1的输入:X1,X2,…Xn, Xi=true or false(1≤i≤n)
- 判定问题L2:判定n个整数中的最大元是否为正数
- L2的输入:Y1,Y2,…Yn, Yi为整数(1≤i≤n)
- 转换函数F:F(X1,X2,…Xn)=(Y1,Y2,…Yn),其中1 Xi=true0 Xi=falseYi=
第30页:多项式归约的意义
3010.1.2 NP难度和NP完全类
- 约化的直观意义:L1可归约为L2,则L2的时间复杂度高于L1的时间复杂度。L1不比L2难。
- 传递性
- “多项式归约”:变换输入的方法能在多项式时间内完成。
- 一个问题归约为另一个问题,时间复杂度增加了,问题的应用范围也增大了。
- 定义:同时满足下面两个条件的问题是NP完全(NPC)问题。①它是一个NP问题②所有的NP问题都可以归约到它。只满足②的问题是NP-hard(难)问题。NP-hard比NPC范围广,指没找到多项式解法的问题,没限定属于NP
第31页:P与NP是否相等
31NP完全问题(NPC问题)
- P=NP或者P≠NP?剑桥大学的克雷数学研究所提供了一百万美金奖金给可以证明P=NP或P≠NP的人,尚未有人能提出证明,这使得此问题成为著名的数学中未解决的问题。
- 人们发现还有一系列的特殊NP问题,其特殊性质使人相信P≠NP,但现在还无法证明。这类特殊的NP问题就是NP完全问题(NPC问题,C代表complete)
第32页:NPC问题的性质
32NPC问题是否能在多项式时间中解决?
- NPC问题的性质:NP完全理论指出在NPC问题具有以下性质:若其中一个问题获得多项式算法,则这一类问题就全部获得了多项式算法;反之,若能证明其中一个问题是多项式时间内不可解的,则这一类问题就全部是多项式时间内不可解的。
- 不能给出使其获得多项式时间的方法
- 也不能说明这样的算法不存在
- 证明许多尚不知是否存在多项式时间的算法之间在计算上是相关的。NP完全问题(NPC问题)
第33页:NPC问题的证明方法
3310.1.2 NP难度和NP完全类
- 证明一个问题是NPC问题
- 是一个NP问题
- 一个已知的NPC问题能约化到它
第34页:NPC概念的提出
34NPC问题
- R. Karp最早给出了NPC的概念,但哪个问题满足定义所要求的条件,当时并不知道;
- 1971年S. Cook发表了“The Complexity of TheoremProving Procedures”的论文,找到了第一个NPC问题;
- 1972年R. Karp发表了“Reducibilty AmongCombinatorial Problems”,从此奠定了NP完全理论的基础。
- 此后又陆续发现很多NPC问题,现已超过3000个
- NPC问题是难解的问题,例如哈米尔顿回路/路径问题,货郎担问题,集团问题,最小边覆盖问题(注意和路径覆盖的区别)等很多问题都是NPC问题,都是难解的问题。
第35页:本章小结
35小结
- 哪些问题是计算机实际可计算的
- 已经证明的非多项式时间问题
- 目前不能证实是否存在多项式时间算法的问题P问题顽型问题NP问题判定问题P与NP的关系NPC问题约化SAT问题Cook定理理论可计算C问题