国科大中科院算法讲义第八章

1、算法复杂性与NPC问题问题与算法的描述 图灵机与确定性算法 NP类问题 NP完全问题 证明问题为NP完全的方法 NP困难问题 P、NP、co-NP的思考 问题与算法的描述 问题问题(problem)：有待回答、通常含有几个取值还未确定的自由变量的一般性提问(question)。 表示符号： 问题的构成问题的构成： 1)对其关于参数的一般性描述； 2)对该问题的答案所应满足的某些特性的说明。 问题的实例问题的实例：指定问题中所有参数的具体取值 。表示符号： 旅行商问题： 参数描述：n个城市C1,C2,Cn，城市间距离d(Ci,Cj) 答案描述：城市的排序：C(1) , C(2) , C(n) ，

2、最小化目标值: 1in-1 d(C(i) , C(i+1) ) + d(C(n) , C(1) ) 旅行商问题实例: n=4, C1 , C2 , C3 , C4 , d(C1,C2)=10, d(C1,C3)=5, d(C1,C4)=9, d(C2,C3)=6, d(C2,C4)=9, d(C3,C4)=3 答案：C1, C3, C4,C2, 长度: 27判定问题及描述 判定问题：答案只有“是”与“非”两种可能的问题。 实例集合D，回答为“是”的集合 Y 描述方法：分成两个部分 例例：用诸如集合、图、函数等各种描述分量来刻画判定问题的一般性例子; 问问：陈述基于一般性例子所提出的一个“是非”

3、提问。 旅行商问题： 例例 待访问城市的有限集合C=C1,C2,Cn、每对城市之间的距离 d(Ci,Cj)Z+ 以及一个界 BZ+ 。 问问 在C中存在一个总长不超过B的、通过所有城市的旅行路线吗？即是否存在的一个排序：C(1) , C(2) , C(n) ，使得 1in-1 d(C(i) , C(i+1) ) + d(C(n) , C(1) ) B 算法算法(algorithm)是指用来求解某一问题的、带有一般性的一步一步的过程。是计算流程的抽象形式，超越实现细节。 问题和语言 算法的性能的合理刻划：计算模型、问题实例的规模 计算模型：图灵机（TM）、随机存储机（RAM）等； 问题实例的规模

4、：描述或表示它所需要的信息量。 编码策略：从某一字符集中选取所需字符构成有限长字符串。合理的编码策略具有可解码性、简洁性，常利用结构化字符串，通过递归、复合等方式给出。对于问题实例 I，在一个合理的编码策略 e 下，描述该实例的字符串中的字符个数称为该问题的输入长度，也作为该问题实例的输入规模。 旅行商问题的一个实例：字符集C,/,0,1,2,3,4,5,6,7,8,9，编码字符串：C1C2C3C4/10/5/9/6/9/3 ，输入长度为32。 长度多项式相关：LengthIp(|x|) 且 |x|q(LengthI) 语言：字符集中字符组成的一些有限长字符串的集合L * L,e=x*|x为某

5、个例子IY在 e 下的编码图灵机的构成 图灵机图灵机：一个具有存储载体的、按照具体指令可完成向左或向右移动、放置标记、抹去标记以及在计算终止时停机等四种基本操作的虚拟机器，可以看作是描述算法的语言。 确定性单带图灵机确定性单带图灵机( DTM )的组成的组成：一个有限状态控制器、一个读写头、一条双向的具有无限多个格的线性带。 DTM程序规定如下信息程序规定如下信息： 1. 字符取用集，其包含输入字符集及空白符b 。 2. 一个有限状态集Q，包含初始状态q0和两个停机状态qY，qN 3. 一个转移函数：(QqY , qN) Q l, r有限状态控制器 -5 -4 -3 -2 -1 0 1 2 3

6、 4 5 6 7 8 读写头确定性算法 图灵机程序的运行图灵机程序的运行：将输入字符串x一格一个字符地存放在带格1到带格|x|中，所有其它的带格均存放空白字符 b。读写头位于带格1，状态控制器处于初始状态，即开始按转移函数指令一步一步地运行：若当前状态q是停止状态qY或qN，则停止，并分别回答“是”或“非”。若当前状态q既不是qY也不是qN，则按照转移函数 (q , s) = (q, s, )读写头首先擦掉当前带格的字符s，并写上字符s,然后依照=l或 r 将读写头向左或右移动一格，最后将当前状态q更新为q 。 图灵机程序M所识别的语言： LM=x*|M作用于x时，停机于状态qY 算法算法：当

7、一个DTM程序对定义于其输入字符集上的所有可能字符串均（在有限步内）停机时，称其为一个算法。 DTM程序M求解问题：M是算法，且 LML( , e )。复杂性函数定义 一个DTM程序M对于输入 x 的计算时间定义为该程序从开始直至进入停机状态为止所运行的步数。 DTM程序M的时间复杂性函数定义：TM: Z+ Z+ TM(n)=maxm|存在x*，|x|=n，使得M对x的计算时间为 m 多项式时间DTM程序：存在多项式 p(x) ，使得 TM(n) p(n) P-语言类： P=L|存在多项式时间程序M，使得L=LM 多项式问题 : 存在多项式时间DTM程序M，其在编码策略e下求解，即 L (,e

8、)P。称为P-类问题。 P-类语言只能描述具有多项式时间确定算法的问题。非确定性单带图灵机 非确定性图灵机包括多值模型、猜想模块模型 多值模型规定如下信息： 1. 字符取用集，其包含输入字符集及空白符b 。 2. 一个有限状态集Q，包括初始状态q0和两个停机状态qY，qN 3. 一个多值转移函数：(QqY , qN) 2 Q l, r (q , s ) = S Q l, r 非确定性图灵机可以被想象为在同一时刻能够独立、并行地完成多种运算（表现在转移函数的多值性）。 猜想模块模型：加一个猜想模块猜想模块有限状态控制器 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 猜想头读写

9、头多值性模型与确定性模型示意 拒绝接受非确定型计算接受或拒绝确定型计算猜想模块模型 猜想模块有一个只进行写操作的猜想头； 计算进程分为两个阶段：猜想阶段和验证阶段 首先，输入字符串x被写在从1到|x|的带格中，其余为空白符。猜想头位于带格-1处，有限状态控制器的读写头处于带格1的位置，有限状态控制器处于不起作用状态。 其次，猜想模块处于起作用状态，一次一步地指示猜想头：要么在被扫描的带格中写下中的一个字符,并向左移动一格；要么停止 猜想模块停止，有限状态控制器即开始起作用，它首先处于初始状态q0，然后就按照DTM完全相同的规则进行。这是检验阶段，由猜想头写出的字符串也被考虑。停机qY，称为可接

10、受的计算。 对于一个给定的输入字符串x，NDTM程序M将会做无限多个可能的计算。如果这些计算中至少有一个为可接受的计算，则称NDTM程序M接受字符串 x。 LM=x | 程序M接受xM所识别的语言NDTM的时间复杂性函数 程序NDTM接受x的时间：在M对于x的所有可接受计算中，程序从一开始直到停机状态为止在猜想和检验阶段所进行的步数的最小值 。 NDTM程序M时间复杂性函数定义：TM: Z+ Z+ TM(n)=maxm | 存在xLM，|x|=n， 使得M接受x所需的计算时间为 m 多项式时间NDTM程序M：存在多项式p(x)，使得TM(n)p(n)。 NP语言类：NP=L|存在多项式时间ND

11、TM程序M，使L=LM NP类问题：存在合理编码策略e，使得L,eNP。 任何现有的计算模型都可以通过加上一个类似于NDTM中的带有只写头的猜想模块来扩充，而且所有如此得到的计算模型在多项式时间内可相互转换的意义下将是等价的。没有必要特别提及NDTM模型，将简单地说“多项式时间不确定算法多项式时间不确定算法”，并将NP类语言与所有可用多项式时间不确定算法求解的判定问题等同看待。 无向图的团问题 问题描述：例例：给定一个有n个顶点的无向图G=(V,E)及整数 k问问：G是否包含一个具有k个顶点的完全子图（团）？ 问题实例的字符串表示：G邻接矩阵，长度：m=n2+logk +1 CLIQUE=w#

12、v | w, v0,1*，以w为邻接矩阵的图G有 一个k顶点的团，v是k的二进制表示 非确定性算法设计第一阶段：将输入字符串w#v进行分解，计算n=|w|1/2以及用v表 示的整数k。若输入不具有形式w#v或|w|不是平方数，则拒绝。第二阶段：非确定性选择V的一个k元子集V ,并用其集合特征向 量表示A1.n。第三阶段：确定性地检查V的团性质。若V是一个团则接受， 否则拒绝。团问题选择子集的非确定性算法 integer j,m; j:=0; for i to n do m:=choice(0,1); case: m=0: Ai:=0; m=1: Ai:=1; j:=j+1; endcase e

13、ndfor if jk then failure; endif 第一阶段可在O(n2)内完成。第二阶段可在O(n)内完成；第三阶段可在O(k2)内完成。总的时间复杂度为 O(n2+k2)定理：对于每一个NP问题，都存在多项式 p ( x ) 使 得 问 题 可 以 用 一 个 时 间 复 杂 度为O(2p(n)的确定性算法求解 证明证明：设A为求解的一个多项式时间不确定性算法，其时间复杂性由一个多项式q(n)来界定。不失一般性，设q可在多项式时间内被估值。因此，对于长度为 n 的每个被接受的输入，必然存在字符集上长度至多为q(n)的某个猜想字符串，使算法A的检验阶段在不多于q(n)步内回答“是

14、”。若| |=k，则所需要考虑的可能猜测的数目最多为kq(n)。对于一个长度为 n 的给定输入，通过应用算法A的确定性检验阶段到相应的kq(n)多个可能猜测字符串中的每一个，直到停止或运行q(n)步，我们可以肯定地发现A对于该输入是否有一个可接受计算。如果A在该时间界内遇到一个导致可接受计算的猜测串，则该模拟过程回答“是”；否则回答“非”。这显然形成了一个求解的确定性算法，而且该算法的时间复杂度将以q(n)kq(n) 为上界。其等价于O(2p(n) 。 NP完全问题(1) 在非确定性图灵机上时间复杂性为q(n)的判定问题与在确定性图灵机上时间复杂性为 q(n)kq(n) 的问题相当。 P NP

15、 ，问：P = NP ？ 研究NP类中问题之间的关系，从NP中找出一些具有特定性质的、与P中问题有显著不同的问题。形成了NP完全理论 多项式变换多项式变换：语言L11*到另一个语言L22*的多项式变换是指映射f: 1* 2*，满足下面两个条件： 1. 存在计算 f 的一个多项式时间DTM程序； 2. 对于所有的x1*有：xL1当且仅当f(x) L2。 记号： L1 L2 。 1 2 如果 L(1 , e1) L(2 , e2) NP完全问题：称一个语言L(判定问题)是NP完全的，如果LNP( NP )，而且，对于任意LNP( NP )都有 L L ( ) NP完全问题(2) 几个性质： 1.

16、若L L, LP，则L P; 2. 若L L，L L, 则 L L 3. 若判定问题是NP完全的，P NP，则NPP； 4. 若L , L NP， L L 则 L NPC LNPC。 几个典型的NP完全问题 1. 可满足性问题 例：给定布尔变量之集以及上子句的一个集合C。 问：是否存在的一个真值分配，使得C是可满足的。 2. 图的顶点覆盖问题 例：给定一个图G(V,E)和一个正整数K|V| 。 问：是否存在G的一个顶点数不超过K的覆盖？NP完全问题(3) 3. Hamilton回路问题 例：给定一个图G(V,E)。 问：G含有一个Hamilton回路吗？ 4. 划分问题 例：已知一个有限集合A

17、，其每个元素a都赋予一个权值s(a)Z+ 问：是否存在A的子集A使得aA s(a) = aAA s(a)。 5.三元可满足性问题 3SAT 例：给定布尔变量的一个有限集合U及定义于其上的子句集C=c1,c2,cm, 其中|ci|=3, i=1,2,m。 问：是否存在U之上的一个真值分配，使得C中所有的子句均被满足？ 6. 三元精确覆盖问题 例：给定有限集X，|X|=3q，以及X的三元子集族C。 问：C含X的一个精确覆盖吗？即存在C C，使得 cC c=X，而且X中的每个元素恰属于C的一个子集。P=np证明新问题是NPC问题的方法(1) 证明 ；选取一个已知的NP完全问题 ；构造一个从 到 的变

18、换 ；证明 为一个多项式变换。Cook定理： 可满足性问题是NPC问题。例例1 1 证明三元可满足性问题是NPC问题。 选择满足性问题作为参照物。设布尔变量集 及子句集 构成SAT的一个一般性例子。我们构造新的布尔变量集 及定义其上的三元子句集 ，使得 可满足当且仅当 可满足。 对于每个子句 ，设 ，其中， 表示 中变量的非的全体。分三种情况讨论： 1) 情形，此时令NPff12 ,nUu uu12 ,mCc ccUCCCjc12jkczzzizUUUU1k 证明新问题是NPC问题的方法(2) 情形2： ，令 情形3: ，令 ；情形4： ，令 ； 最后，令 ，往证： 可满足当且仅当 可满足设

19、是使 满足的一个真赋值。以下说明 可扩充成满足 的一个真赋值： 。 因为 中的变量可分解成不同的集合 ，而每个 的变量仅出现在属于 的子句中，我们仅需要说明如何将 扩充到各个 即可，且证明在上述四种情形的每一种情形下， 中的所有子句均被满足。12121212121111,jjjjjjjjjjjjUyyCzyyzyyzyyzyy2k 1111212,jjjjjUyCzzyzzy3k jjjcCU,3k |13ijjUyik 1131221|14iikjjjijjkkCzzyyzyikyzz miimiiCCUUU11, CC,:FTUtCtC,: FTUtUUmjUj1, jUjCtjUjC证明

20、新问题是NPC问题的方法(3)若 属于情形 或情形 ，则 中的子句已被 所满足，从而可任意地扩展它到 ，例如，对所有的 ，令 若 是由情形 所确定的，那么 为空集，而 的赋值已经使 中的单个子句取真值。 若 是由情形 所确定的，因为 为 的一种可满足性真赋值，必然存在一个最小的整数 ，使得变量 在 之下被赋予真值，且 。若 为1或2，则可对 令 ；若 为 或 ，则对于 ，令 ；其余情况，令 ， 。 容易证明，这些选择将保证 中所有的子句均被满足，进而 中的所有子句也均被赋值 所满足。反之，若 为 的一个可满足性真赋值，则不难证明 对于 中变量的限制必形成对 的一个可满足性真赋值。jU1k2kj

21、CtjUjUyTyt)( jU3kjUtjjcC jU3ktCllzt0l l31:kiiFytij)( l1kk31:kiiTytij)( ()12ijt yTil ，31)( kilFytij，jCC t tC tUC证明新问题是NPC问题的方法(4)至此，我们证明了 可满足当且仅当 可满足。 要证明上述变换可在多项式时间内完成，只需注意到 中三元子句的数目被 的一个多项式所界定。也就是说，3SAT例子的大小由SAT例子的大小的一个多项式函数所界定。由此，根据上述构造方法，不难证明它是一个多项式变换。 例例2 证明图的顶点覆盖问题VC是NPC-问题 首先，图的顶点覆盖问题是NP问题。因为求

22、解它的不确定性算法只需猜测顶点的一个子集，然后在多项式时间内就可以检验该子集是否包含每条边的至少一个端点，并具有适当的大小，即该顶点子集中顶点的个数不超过限定的值。 选三元可满足性问题做参照物。设 为3SAT的一个一般性例子。我们要构造一个图 和一个正整数 ，使得 有一个顶点数不超过 的覆盖，当且仅当CCCnm1212:,nmUuuuCccc),(EVG |VK GK证明新问题是NPC问题的方法(5) 是可满足的。 对每个变量 ,定义 ，其中 ；对于每个子句 ，设 ，构造一个三角形 ，其中并且构造新的边集 ，如下图。 CUui),(iiiEVT ,( ,)iiiiiiVu uEu uCcjjj

23、jjcxyz),(jjjEVS 123121323( ),( ),( ) ,( ),( ) ,( ),( ) ,( ),( )jjVA jAjAjEA jAjA jAjAjAj 123( ),( ),( ),jjjjEA jxAjyAjzSju1u2u3u4unv1v2v3v4vnA1(j)A2(j)A3(j)A3(k)A2(k)A1(k)xjyjzjxkykzk证明新问题是NPC问题的方法(6) 其中 。令 ，由于 ，以及 均为有 限值，上述构造图的过程一定在多项式时间内完成。以下证明： 是可满足的当且仅当G有一个顶点数不超过 的覆盖。 设 是G的一个顶点覆盖， 。由图G的构造， 必然包含每

24、 个 中至少一个顶点，和每个 中至少两个顶点，这已经给出了至 少 个顶点，故 必然含有每个 中恰好一个顶点和每个 中恰好两个顶点。据此给出U的一种真赋值 如下： 当 时， ；而 时， 。 为了说明该赋值满足每个子句 ，考虑 中的三条边。这些边 中恰有两条可被 中的顶点覆盖，剩下的一条边必由属于 的 某个 中的一个顶点覆盖。但这意味着子句 中的相应变量，或niuvii, 2 , 1,11111,nmnmmijijjijijjVVVEEEEEVG,mnK2| 23 ,|336VnmEnmmnmKCKVV KV | |ViTjSmnK2ViTjS,:FTUtVuiTuti)(VuiFuti)(Ccj

25、jEVVjViVjc证明新问题是NPC问题的方法(7)者是 或者是 ，在赋值 之下取值为真，从而 可由 满足。反之，如果 为C的一个可满足性真赋值，我们构造G的一个覆盖如下：对于 中的顶点，如果 ，选取 ，如果 则选取 ；对于 中的顶点，由于 中至少有一个取真值 ，不妨设 ，则在前面诸 中顶点的选取中， 必然被选取，此时我们在 中只需选取顶点 、 即可。 上述方法选出的顶点集显然是G的覆盖，而且顶点数恰好为 。 例例3 证明：Steiner树问题是NPC-问题 例：给定图 ，对其每条边 都有相应的权 ，另外有G的顶点子集 ，某个界 。 问：是否存在G的一棵子树 ，使 ，而且 ？ iuiuttj

26、c,:FTUtiVTuti)(iuFuti)(iu)1 (mjVjjjjjcxyzTTxtj)(iVjxjV2( )Aj3( )AjmnK2),(EVG EeZew )(VR ZB),(11EVT EEVVR11,BewEe1)(证明新问题是NPC问题的方法(8) 为证明Steiner树问题是NPC的,选X3C问题作为参照物： 三元子集族 ，构造Steiner树问题的相应例子如下： 取 ，其中 ； 令所有边的权值为1， ， 。显然这一构造过程可在多项 式时间内完成。 qxxxX321,ncccC,21),(EVG 00,|1,|,1,13iijjiVvCX Ev cinc xxcinjq Xv

27、R0qB4。CiqCi2Ci1v0 x1x2x3x3qC/X证明新问题是NPC问题的方法(9)如果 为 的一个精确覆盖，则取 ，其中 ，由于每个 恰好出现在 的某个三元子集里，故 是连通的无圈图，因而是一棵树。而且 。注意到 ，且 ，由此知Steiner树问题的回答为“是”。 反之，若 为 的一棵Steiner树， ，则每个 都是 的顶点。不妨设每个 都是 的叶顶点，因为，否则的话，顶点 的度数大于1，及存在边 删去其中一条边，如 。由于 ， 不可能都属于 ，否则 包含有圈，将不属于 的那条边添入 得到另一棵树 ，它是总权值未变的Steiner树。但这棵树包含X中的顶点作为叶顶点的个数比 的多

28、，这样做下去，必然找到一棵Steiner树，在其上，所有X中的顶点都是叶顶点。再由连通性，每个 恰好和某一个 在 中邻接，令 ，则 显然是 的一个精确覆盖CC X),(11EVT XCccvVii|0110,|,|,13iiijijiEv ccCc xcC xcjqjxCTqE4|11VR BEewEe|)(11) , (EVT ),(EVG VR qjxj31TjxTjx 12,jijix cx cEE1,jix c10,iv c20,iv cETEE1TTjxicT|,13iijCcc xTjqCX证明新问题是NPC问题的方法(10) 例例4 证明 0/1背包判定问题是NPC问题 例：给定

29、一个有限集合 ，对每一个 ，对应一个值 和相应的值 。另外，还有一个容量约束 和一个价值目标 。 问：是否存在 的一个子集 , 使得 ，而且 显然，0/1背包问题是NP问题。 现在，我们考虑特殊的 0/1 背包问题：对所有的 有 , 且取 。 显然，这个0/1背包判定问题回答为“是”当且仅当集合 的划分问题回答为“是”。可见，划分问题恰是0/1 背包问题的特例。从而由划分问题是NPC问题推得0/1背包判定问题是NPC问题。 XxX( )w xZ( )p xZMZZKXXX( )x Xw uM( )x Xp xKxX( )( )w xp x1( )2x XMKw xXNP难问题(1) 图灵归约图

30、灵归约：设 和 是两个问题，称 可图灵归约为 ，记作 ，如果存在求解 的一个算法 ，它多次调用求解 的算法 作为其子程序。 库克归约库克归约：假设 ，且求解 的程序 每次调用求解 的子程序 均需用单位时间，若 为一个多项式时间确定算法。称 为从 到 的多项式归约。（也称库克归约）。 库克归约的定义不限于判定问题，也可适用于函数类问题（如最优化）。如果问题 可以归约到 ，则 至少和 一样难。 NP难问题：难问题：对于问题 ，如果存在一个NP完全问题 ，使得 可多项式时间图灵归约到 ，则称 是NP困难的。 NP难问题不要求是NP类问题。 第 重子集问题 例：已知整数 ； 问：存在 个不同的子集 ，

31、使得对于 有 ？121212T 11A22A2A1A1A121221kLkcccn,21k12,1,2, kS SSnki, 1 LciSjj12T 1A21NP难问题(2) 利用划分问题(NP完全问题)证明第k最重子集问题是NP难问题 事实上，设 是划分问题的一般例子，假设我们已经 有个算法 可以用来解第 最重子集问题，则可设计出求解 划分问题的算法如下： 首先，若 为奇数，则立即推出回答问题否。现在，假定 是偶数，并令 ，用算法 作为子程序，按下列二分 搜索技术确定重至少是 的不同子集的数目 ： 1) 令 ； 2) 若 ，置 ，且停机； 3) 令 ，并调用算法 。 4) 若回答为“是”，则

32、令 ，转2)；否则，令 ，转2) 以上过程通过恰好 次调用 ,即可找到 。至此，只需再调 用一次该算法即可给出所考虑划分问题例子的答案，即调用 。若该调用的答案为“是”，则S中所有重至少为L的子 集也必满足其重至少为L+1，因此，S没有重为L的子集，故对划分 问题的回答为“否”。相反，若该调用的回答为“否”，则意味着 存在,21ncccS,LkSAkniic1niic1niicL121,LkSAL*KnKK2, 0maxmin1minmax KKmin*KK 2/ )(maxminKKK,LKSAKKminKKmaxn,LKSA*K 1*,LKSANP难问题(3)某一个S的子集，使得其重为L，

33、对划分问题的回答为“是”。 由上述迭代过程容易看出，若假设每次调用算法A只需要单位时间，则以上即给出了求解划分问题的一个多项式时间算法。也就是说，我们证明了划分问题可多项式时间归约到第k个最重子集问题。 旅行商问题是NP难问题 旅行商问题不是NP的。因为对其解的任一猜想，要检验它是否是最优的，需要同所有其它的环游比较，这样的环游会有指数多个，因而不可能在多项式时间内完成。 用图的Hamilton回路问题(NPC问题)证明旅行商问题是NP难的 已知无向图G=(V,E),|V|=n,构造其对应的旅行商问题如下：这一变换可以在多项式时间内完成，而且，图G有Hamilton回路的充要条件是上述构建的旅行商问题有解，且其解对应的路程长度为n。故我们证明了对称旅行商问题是NP