计算机算法设计与分析：第10章 NP难度和NP完全问题

1、1第十章第十章NP难度和难度和NP完全问题完全问题210.1 基本概念基本概念 10.1.1 不确定算法不确定算法 10.1.2 NP难度和难度和NP完全类完全类3预备知识预备知识p算法时间复杂度的渐进表示算法时间复杂度的渐进表示 上界上界O，下界，下界 p多项式时间算法与非多项式时间算法多项式时间算法与非多项式时间算法检索：检索：O(logn) 排序：排序：O(nlogn)货郎担问题：货郎担问题：O(n22n) 背包问题：背包问题：O(2n/2)算法的时间复杂度一旦大于多项式时间，算法的执行时算法的时间复杂度一旦大于多项式时间，算法的执行时间会随间会随n的增大而急剧增加。即使中等规模的问题也

2、解的增大而急剧增加。即使中等规模的问题也解不出。不出。 10.1 基本概念基本概念4问题复杂性和算法复杂性的区别问题复杂性和算法复杂性的区别p算法的复杂性是指解决问题的一个具体的算法的执行时算法的复杂性是指解决问题的一个具体的算法的执行时 间，这是算法的性质；间，这是算法的性质；p问题的复杂性是指这个问题本身的复杂程度，是问题的性问题的复杂性是指这个问题本身的复杂程度，是问题的性质。质。 例：排序问题，如果只能通过元素间的相互比较来确定元例：排序问题，如果只能通过元素间的相互比较来确定元素间的相互位置，而没有其他的附加可用信息，则排序问素间的相互位置，而没有其他的附加可用信息，则排序问题的复杂

3、性是题的复杂性是O(nlgn) 但是排序算法很多，冒泡法是但是排序算法很多，冒泡法是O(n2)，快速排序平均情况，快速排序平均情况下是下是O(nlgn)等等，排序问题的复杂性是指在所有的解决等等，排序问题的复杂性是指在所有的解决该问题的算法中最好算法的复杂性。该问题的算法中最好算法的复杂性。 问题的复杂性不可能通过枚举各种可能算法来得到，一般问题的复杂性不可能通过枚举各种可能算法来得到，一般都是预先估计一个值，然后从理论上证明。都是预先估计一个值，然后从理论上证明。 5确定算法确定算法运算结果是唯一确定的，对于同样的输入，它的输运算结果是唯一确定的，对于同样的输入，它的输出从不改变。出从不改变

4、。之前介绍的算法都是确定算法之前介绍的算法都是确定算法确定算法可以在确定型图灵机上执行确定算法可以在确定型图灵机上执行不确定算法不确定算法运算结果不是唯一确定的运算结果不是唯一确定的不确定算法可以在非确定型图灵机上执行不确定算法可以在非确定型图灵机上执行10.1.1 不确定的算法不确定的算法6图灵机p19361936年图灵提出了一个抽象计算模型年图灵提出了一个抽象计算模型 图灵机，并图灵机，并用它来精确定义可计算函数。图灵用它来精确定义可计算函数。图灵机的基本思想是模机的基本思想是模拟人用纸笔进行数学运算的过程，这个运算过程可分拟人用纸笔进行数学运算的过程，这个运算过程可分解为下面两种简单的动

5、作：解为下面两种简单的动作：1.1.在纸上写或擦除某个符号；在纸上写或擦除某个符号；2.2.把注意力从纸的一个位置移动到另一个位置。把注意力从纸的一个位置移动到另一个位置。p在每个阶段将由执行运算的人决定下一步的动作，而在每个阶段将由执行运算的人决定下一步的动作，而他的决定依赖于此人当前所关注的是纸上哪个位置的他的决定依赖于此人当前所关注的是纸上哪个位置的符号，以及此人当前思维的状态。符号，以及此人当前思维的状态。 7Turing Machine810.1.1 不确定的算法不确定的算法p不确定的算法不确定的算法 由两个阶段组成：由两个阶段组成：猜测阶段猜测阶段:产生一个任意字符串产生一个任意字

6、符串C,可以看成是问题实例可以看成是问题实例的解的猜测的解的猜测, 可能在不确定性算法的不同次运行中不同可能在不确定性算法的不同次运行中不同.验证阶段验证阶段:是一个确定的可执行子程序是一个确定的可执行子程序. 检查字符串检查字符串C是否是问题实例的解是否是问题实例的解, 若是，算法终止且若是，算法终止且输出输出YES，否则输出，否则输出NO.两阶段都能在多项式时间两阶段都能在多项式时间内完成内完成9函数：函数：choice(S):任意选取集合任意选取集合S中的一个元素中的一个元素 例：例： choice(1:n) 选择区域选择区域1,n中任一整数中任一整数语句：语句：failure: 发出不

7、成功完成的信号发出不成功完成的信号 当且仅当所有的选择都不会导致成功时，算法以不成功当且仅当所有的选择都不会导致成功时，算法以不成功stopsuccess：发出成功完成的信号：发出成功完成的信号 每每当有一组选择导致成功时，算法以成功当有一组选择导致成功时，算法以成功stopfailure 和和success相当于相当于stop语句，无语句，无return的作用的作用choice ，failure 和和success的计算时间均为的计算时间均为O(1)在在SPARKS语言中一个函数和两个语句：语言中一个函数和两个语句：10不确定算法举例不确定算法举例-不确定机上的不确定机上的检索问题检索问题考

8、察给定元考察给定元素集素集A(1:n)，n 1，检索元素，检索元素x是否在是否在A中。中。生成一个随机整数生成一个随机整数j，1 j n；判断；判断A(j)和和x是否相等。是否相等。 jchoice(1:n) if A(j)=x then print(j); success endif print(0); failure 随机产生一个数，不确定的复杂度随机产生一个数，不确定的复杂度O(1) 确定的检索算法的复杂度为确定的检索算法的复杂度为 (n).11不确定算法举例不确定算法举例-不确定机上的分类问题不确定机上的分类问题p设设A(i)是一个待分类的正整数集，设计不确定算法按照非是一个待分类的正

9、整数集，设计不确定算法按照非降次序分类并输出。降次序分类并输出。辅助数组辅助数组B，初始化为，初始化为0逐个将逐个将A中的元素，放入中的元素，放入B(j),j为为“猜测猜测”出的正整数，出的正整数，检查检查B中元素是否按非降次序排列。中元素是否按非降次序排列。procedure NSORT(A,n)integer A(n), B(n), n,i,jB0for i 1 to n do j choice(1:n) if B(j) 0 then failure endif B(j) A(i)repeatfor i 1 to n-1 do if B(i) B(i+1) then failure end

10、ifrepeatprint(B) successend NSORT若若B(j)已被占用，失败已被占用，失败若存在降序，失败若存在降序，失败时间复杂度：时间复杂度：O(n)确定分类算法：确定分类算法： (nlogn)12不确定机在现实技术条件下是不存在的，是为了不确定机在现实技术条件下是不存在的，是为了分析计算机复杂度难题而虚构的理论模型。分析计算机复杂度难题而虚构的理论模型。可以设想不确定机在执行可以设想不确定机在执行choice(S) 语句时，具有语句时，具有主动选择正确值（导致主动选择正确值（导致success）的能力，这是通）的能力，这是通过同时复制大量副本并行实现的。过同时复制大量副本

11、并行实现的。不确定算法的设计思路一般是，先随机生成解，不确定算法的设计思路一般是，先随机生成解，再检查是否为答案。再检查是否为答案。不确定算法的执行不确定算法的执行13只关心唯一输出的不确定算法只关心唯一输出的不确定算法不确定的判定算法只产生不确定的判定算法只产生0/1输出：输出：只需要回答只需要回答yes或者或者no的问题。的问题。0:当且仅当没有一种选择可导致当且仅当没有一种选择可导致success1:当且仅当至少存在一种选择导致当且仅当至少存在一种选择导致success输出隐含于输出隐含于success和和failure，此外无输出语句，此外无输出语句不确定的判定算法不确定的判定算法14

12、判定问题判定问题许多最优化问题都可以转化为判定问题。许多最优化问题都可以转化为判定问题。 很多问题满足性质：很多问题满足性质： 判定问题在多项式时间内求判定问题在多项式时间内求解当且仅当对应的最优化问题可以在多项式时间解当且仅当对应的最优化问题可以在多项式时间内求解，反之亦然。内求解，反之亦然。如果判定问题不能在多项式时间内求解，那么与它相应的如果判定问题不能在多项式时间内求解，那么与它相应的最优化问题也不能在多项式时间内求解。最优化问题也不能在多项式时间内求解。15优化问题表示为判定问题形式优化问题表示为判定问题形式p图着色问题图着色问题： 已知已知n点图点图G=，求对，求对G的的n个顶点进

13、行着色个顶点进行着色的一种方法（相邻顶点颜色不同），使得所用的一种方法（相邻顶点颜色不同），使得所用颜颜色的总数最小色的总数最小。 已知已知n点图点图G=，问图，问图G是否是否可用可用k种颜色种颜色进进行着色？行着色？p优化的结果优化的结果包含包含了判定的结果，但判定的结果了判定的结果，但判定的结果并并不包含不包含优化结果。优化结果。p从判定解不难得到它的最优解。从判定解不难得到它的最优解。 GCD(G,n)GCD(G,n,k) k=2,3,n16优化问题表示为判定问题形式优化问题表示为判定问题形式-最大集团最大集团p最大集团最大集团 G的一个集团的一个集团(clique) ：图图G=的最大完

14、全子图。的最大完全子图。 集团的大小用所含的结点数来量度。集团的大小用所含的结点数来量度。 最大集团问题最大集团问题：确定：确定G内最大集团的大小问题。内最大集团的大小问题。 对应判定问题对应判定问题：对于某个给定的：对于某个给定的k，确定，确定G是否有一是否有一个大小至少为个大小至少为k的集团的集团。17优化问题表示为判定问题形式优化问题表示为判定问题形式-最大集团最大集团pDCLIQUE(G,k) 为集团判定问题的一个确定判定为集团判定问题的一个确定判定算法：算法：1. 设设|V|=n，G内的最大集团的大小可多次应用内的最大集团的大小可多次应用DCLIQUE(G,k)而求得。而求得。2.

15、对于对于k=n, n 1, n 2,直到直到DCLIQUE(G,k)输出为输出为1为止。为止。p如果如果DCLIQUE的时间复杂度为的时间复杂度为f(n),则最大集团的则最大集团的大小可在大小可在n f(n)时间内求出。时间内求出。p如果最大集团的大小可以在如果最大集团的大小可以在g(n)时间内确定，则时间内确定，则其判定问题也可在其判定问题也可在g(n)时间内求出。时间内求出。18优化问题表示为判定问题形式优化问题表示为判定问题形式- 0/1背包问题背包问题0/1背包的判定问题：背包的判定问题：对于给定的非负数对于给定的非负数R，pi和和wi, 1i n,确定是否存在一组确定是否存在一组xi

16、的的0/1赋值，使得赋值，使得 pixiR且且 wixi M 如果如果0/1背包的背包的判定问题不能在多项式时间内求解，判定问题不能在多项式时间内求解，那么与它相应的最优化问题也不能在多项式时间那么与它相应的最优化问题也不能在多项式时间内求解。内求解。19不确定算法的时间复杂度不确定算法的时间复杂度p定义定义10.1 一个不确定算法所需的时间是指当存在一个不确定算法所需的时间是指当存在一选择序列导致一成功完成时，为了完成任意给一选择序列导致一成功完成时，为了完成任意给定的一个输入而达到成功完成所需步骤的最小值；定的一个输入而达到成功完成所需步骤的最小值；在不成功完成的情况下所需的时间是在不成功

17、完成的情况下所需的时间是O(1). 假如对于所有的大小为假如对于所有的大小为n(n n0)的输入的输入,导致成功完导致成功完成需要的时间成需要的时间至多至多为为c f(n)，其中，其中c和和n0是两个常是两个常数，则这个不确定算法的复杂度为数，则这个不确定算法的复杂度为O(f(n).20最大集团判定问题的不确定算法最大集团判定问题的不确定算法procedure DCK(G,n,k)S for i1 to k do t choice(1:n) if t S then failure endif S S trepeatfor 使得使得i S, j S的的每一对每一对(i,j),and i j do

18、 if (i,j)不是此图的边不是此图的边 then failure endifrepeatsuccessend DCKS是是“猜测猜测”的的k个顶点的集合，初值为空集个顶点的集合，初值为空集若若t是一个已生成过的顶点，失败是一个已生成过的顶点，失败k个顶点之间都有边连接个顶点之间都有边连接O(n+k2)=O(n2) =O(m)m为输入长度为输入长度k个不同结点集合个不同结点集合21可满足性问题可满足性问题-概念概念p令令x1,x2,xn表示布尔变量（它们的值既可为真也表示布尔变量（它们的值既可为真也可为假）。命题公式由布尔变量、布尔常量以及可为假）。命题公式由布尔变量、布尔常量以及布尔运算符

19、组成。布尔运算符组成。合取范式合取范式(CNF)：形如形如A1 A2 Am；其中：；其中：Ai为为子句，子句，析取范式析取范式(DNF)：形如形如B1 B2 Bn，Bi是短语是短语22原子：原子：命题的抽象，用大写的英文字母命题的抽象，用大写的英文字母P，Q，等表示。等表示。公式公式：是如下定义的一个符号串：是如下定义的一个符号串：(1)原子是公式；原子是公式；(2)F、T是公式；是公式； (3)若若G，H是公式，则是公式，则( G)，(G H)， (G H)，(GH)，(GH)是公式；是公式；(4)所有公式都是有限次使用所有公式都是有限次使用(1)，(2)，(3)得到的符号串。得到的符号串。

20、可满足性问题：可满足性问题：对于变量的任意一组真值指派，确定公式是对于变量的任意一组真值指派，确定公式是否为真。否为真。CNF可满足性：可满足性：对于对于CNF公式的可满足性问题。公式的可满足性问题。可满足性问题可满足性问题-概念概念23可满足性（可满足性（ SAT）问题问题SAT问题来源于许多实际的逻辑推理类的应用问题。问题来源于许多实际的逻辑推理类的应用问题。是建立是建立NP完全理论的突破点完全理论的突破点。对于一个多项式时间的不确定算法，当且仅当给定对于一个多项式时间的不确定算法，当且仅当给定的命题公式的命题公式E(x1,x2,xn)是可满足的。则算法成是可满足的。则算法成功终止。功终止

21、。p可满足性问题的不确定算法思想：从可满足性问题的不确定算法思想：从2n组可能的组可能的真值指派中不确定地选取一组赋给真值指派中不确定地选取一组赋给 (x1,x2,xn)验验证其对给定的命题公式证其对给定的命题公式E(x1,x2,xn)是否为真。是否为真。24procedure EVAL(E,n)boolean x(n)for i1 to n do xi choice(true,false)repeatif E(x1,x2,xn)=true then success else failureendifend EVAL 对对n个变量赋予个变量赋予一组真值指派一组真值指派不确定时间为不确定时间为O

22、(n)25说明说明p为了研究问题的复杂性，必须将问题抽象，为了为了研究问题的复杂性，必须将问题抽象，为了简化问题，我们只考虑一类简单的问题，判定性简化问题，我们只考虑一类简单的问题，判定性问题。问题。p任何一般的最优化问题都可以转化为一系列判定任何一般的最优化问题都可以转化为一系列判定性问题；性问题；p如果一个判定性问题的复杂度是该问题的一个实如果一个判定性问题的复杂度是该问题的一个实例规模例规模n的多项式函数，则我们说这种可以在多的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题属于项式时间内解决的判定性问题属于P 类问题。类问题。P类类问题就是所有复杂度为多项式时间的问题集合。问

23、题就是所有复杂度为多项式时间的问题集合。 2610.1.2 NP难度和难度和NP完全类完全类p定义定义10.2：P是所有可在多项式时间内用是所有可在多项式时间内用确定算法求解的判定问题确定算法求解的判定问题的的集合。集合。NP是所有可在多项式时间内用是所有可在多项式时间内用不确定算法求解的判定问题不确定算法求解的判定问题的的集合。集合。p存在不是存在不是NP问题的问题问题的问题：猜到一个解，但不能在多项式时间内验证：猜到一个解，但不能在多项式时间内验证它。它。pP NP （所有所有P类问题都是类问题都是NP问题问题，确定算法是不确定算法的特例），确定算法是不确定算法的特例）p注：注：NP问题不

24、一定都是难解的问题，比如：简单的数组排序问题是问题不一定都是难解的问题，比如：简单的数组排序问题是P类问题，但类问题，但P属于属于NP，也是，也是NP问题问题pNote：NP问题不是非问题不是非P类问题类问题 pP NP ？ PNP ？由此研究产生了由此研究产生了cook定理定理NP问题是指可以用不确定算法在多项式时间里验证一个解的问题问题是指可以用不确定算法在多项式时间里验证一个解的问题另一个定义：可以用不确定算法在多项式时间里猜出一个解的问题另一个定义：可以用不确定算法在多项式时间里猜出一个解的问题27cook定理定理p【cook定理】可满足性定理】可满足性(SAT)在在P内，当且仅当内，

25、当且仅当P=NP。 SAT问题如果有多项式解，当且仅当问题如果有多项式解，当且仅当P=NP2810.1.2 NP难度和难度和NP完全类完全类 定义定义10.3（约化）：（约化）：令令L1和和L2是两个问题，如果有一确定是两个问题，如果有一确定的多项式时间算法求解的多项式时间算法求解L1，而这个算法使用了一个在多项，而这个算法使用了一个在多项式时间内求解式时间内求解L2的确定算法，则称的确定算法，则称L1约化为约化为L2（L1L2）问题问题L1约化为问题约化为问题L2的含义是：的含义是：可以用问题可以用问题L2的解法解决的解法解决问题问题L1，或者说，问题，或者说，问题L1可以可以“变成变成”问

26、题问题L2p判定问题判定问题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约化举例约化举例p判定问题判定问题L1：判定：判定n个布尔值中是否至少有一个为个布尔值中是否至少有一个为true.pL1

27、的输入：的输入：X1,X2,Xn, Xi=true or false(1 i n)p判定问题判定问题L2：判定：判定n个整数中的最大元是否为正数个整数中的最大元是否为正数pL2的输入：的输入：Y1,Y2,Yn, Yi为整数为整数(1 i n)p转换函数转换函数F:F(X1,X2,Xn)=(Y1,Y2,Yn),其中其中 1 Xi=true 0 Xi=falseYi=3010.1.2 NP难度和难度和NP完全类完全类p约化的直观意义约化的直观意义： L1可归约为可归约为L2，则，则L2的时间复杂度高的时间复杂度高于于L1的时间复杂度。的时间复杂度。 L1不比不比L2难。难。p传递性传递性p“多项式

28、归约多项式归约”：变换输入的方法能在多项式时间内完成。：变换输入的方法能在多项式时间内完成。p一个问题归约为另一个问题，时间复杂度一个问题归约为另一个问题，时间复杂度增加了增加了，问题的，问题的应用范围也增大应用范围也增大了。了。p定义：同时满足下面两个条件的问题是定义：同时满足下面两个条件的问题是NP完全完全(NPC)问题问题。 它是一个它是一个NP问题问题 所有的所有的NP问题都可以归约到它。问题都可以归约到它。 只满足只满足的问题是的问题是NP-hard（难）问题（难）问题。NP-hard比比NPC范围广，指没找到多项式解法的问题范围广，指没找到多项式解法的问题, 没限定属于没限定属于N

29、P 31NP完全问题（完全问题（NPC问题）问题）pP=NP或者或者PNP？剑桥大学的克雷数学研究所提供剑桥大学的克雷数学研究所提供了一百万美金奖金给可以证明了一百万美金奖金给可以证明P=NP或或PNP的人，的人，尚未有人能提出证明，这使得此问题成为著名的数尚未有人能提出证明，这使得此问题成为著名的数学中未解决的问题。学中未解决的问题。p人们发现还有一系列的特殊人们发现还有一系列的特殊NP问题，其特殊性质问题，其特殊性质使人相信使人相信P NP，但现在还无法证明。这类特殊的，但现在还无法证明。这类特殊的NP问题就是问题就是NP完全问题（完全问题（NPC问题，问题，C代表代表complete）32NPC问题是否能在多项式时间中解决？问题是否能在多项式时间中解决？pNPC问题的性质：问题的性质： NP完全理论指出在完全理论指出在NPC问题具问题具有以下性质：若其中一个问题获得多项式算法，则有以下性质：若其中一个问题获得多项式算法，则这一类问题就全部获得了多项式算法