1、l将能在多项式时间求解的问题看作将能在多项式时间求解的问题看作(tractable problem)，而将至今尚未找到多项式时，而将至今尚未找到多项式时间算法求解的问题视为间算法求解的问题视为(intractable problem)。l为便于研究，先假定一种运行不确定算法的抽为便于研究，先假定一种运行不确定算法的抽象计算模型，该抽象机除了包含第象计算模型，该抽象机除了包含第2.1.3节的抽象节的抽象机模型的基本运算外，最根本的区别在于它新增机模型的基本运算外，最根本的区别在于它新增了下面一个新函数和两个新语句：了下面一个新函数和两个新语句：l（1）Choice(S)：任意选择集合：任意选择集
2、合S的一个元素；的一个元素；l（2）Failure：发出不成功完成信号后算法终止；：发出不成功完成信号后算法终止；l（3）Success：发出成功完成信号后算法终止。：发出成功完成信号后算法终止。在在n个元素的数组个元素的数组a中查找给定元素中查找给定元素x，如，如果果x在其中，则确定使在其中，则确定使aj=x的下标的下标j，否则输出，否则输出-1。l包含包含Choice函数的算法能按如下既定方式执行：函数的算法能按如下既定方式执行：当算法执行中需作出一系列的当算法执行中需作出一系列的Choice函数选择时，函数选择时，当且仅当对于当且仅当对于Choice的任何一组选择都不会导致成的任何一组选
3、择都不会导致成功信号时，此算法在功信号时，此算法在O(1)时间不成功终止；否则，时间不成功终止；否则，只要存在一组选择能够导致成功时，算法总能采取只要存在一组选择能够导致成功时，算法总能采取该组选择使得算法成功终止。该组选择使得算法成功终止。l包含不确定选择语句，并能按上述方式执行一个包含不确定选择语句，并能按上述方式执行一个算法的机器称为算法的机器称为（non deterministic machine）。在不确定机上执行的算法称为）。在不确定机上执行的算法称为（non deterministic algorithm）。）。lvoid NSort(int a,int n)ll int bmS
4、ize,i,j;l for(i=0;in;i+)bi=0;l for(i=0;in;i+)l j=Choice(0,n-1);l if(bj)Failure();l bj=ai;l l for(i=0;ibi+1)Failure();for(i=0;in;i+)coutbi ;coutendl;Success();（不确定算法时间复杂度）一个不确（不确定算法时间复杂度）一个不确定算法所需的时间是指对任意一个输入，当存在定算法所需的时间是指对任意一个输入，当存在一个选择序列导致成功完成时，达到成功完成所一个选择序列导致成功完成时，达到成功完成所需的最少程序步。在不可能成功完成的情况下，需的最少程
5、序步。在不可能成功完成的情况下，所需时间总是所需时间总是O(1)。（最大集团及其判定问题）无向图最大集团及其判定问题）无向图G=(V,E)的一个完全子图称为该图的一个的一个完全子图称为该图的一个（clique）。）。集团的规模用集团的顶点数衡量。集团的规模用集团的顶点数衡量。确定图确定图G的最大集团规模的问题。的最大集团规模的问题。（G,k）是对给定正整数）是对给定正整数k，判定图，判定图G是否存在一是否存在一个规模至少为个规模至少为k的集团。的集团。lvoid Clique（int gmSize,int n,int k）llS=;lfor(int i=0;i k;i+)lint t=Choi
6、ce(0,n-1);lif(t S)Failure();lS=St;llfor(对所有对所有(i,j)，i S，j S且且i j)lif(i,j)E)Failure();lSuccess();l 可满足性问题可满足性问题（satisfiability problem）是一个判定问题，它确定对于一个给定的命题公是一个判定问题，它确定对于一个给定的命题公式，是否存在布尔变量的一种赋值（也称真值指式，是否存在布尔变量的一种赋值（也称真值指派）使该公式为真。派）使该公式为真。是指判定一个是指判定一个CNF公式的可满足性。公式的可满足性。void Eval(CNF E,int n)int xmSize;
7、for(int i=1;i=n;i+)xi=Choice(0,1);if(E(x,n)Success();else Failure();（P P类和类和NPNP类）类）P P是所有可在多项式时间是所有可在多项式时间内用确定算法求解的判定问题的集合。内用确定算法求解的判定问题的集合。NPNP是所有可是所有可在多项式时间内用不确定算法求解的判定问题的集在多项式时间内用不确定算法求解的判定问题的集合。合。（多项式约化）令（多项式约化）令Q1和和Q2是两个问题，是两个问题，如果存在一个确定算法如果存在一个确定算法A求解求解Q1，而算法，而算法A以多项以多项式时间调用另一个求解式时间调用另一个求解Q2的
8、确定算法的确定算法B。若不计。若不计B的的工作量，算法工作量，算法A是多项式时间的，则称是多项式时间的，则称Q1约化约化（reduced to）为）为Q2，记做，记做。若若Q1 P，Q2Q1，则有，则有Q2 P。若若Q1Q2，Q2Q3，则，则Q1Q3。（NP难度）对于问题难度）对于问题Q以及任意问题以及任意问题Q1 NP，都有，都有Q1Q，则称，则称Q是是NP难度难度（NP hard）的。的。（NP完全）对于问题完全）对于问题Q NP，Q是是NP难难度的，则称度的，则称Q是是NP完全完全（NP complete）的。）的。l如何确定某个问题如何确定某个问题Q是否是是否是NP难度的？一般的证难度
9、的？一般的证明策略由以下两步组成：明策略由以下两步组成：l（1）选择一个已经证明是）选择一个已经证明是NP难度问题难度问题Q1；l（2）求证）求证Q1Q。l由于由于Q1是是NP难度的，因此所有难度的，因此所有NP类问题都可约化类问题都可约化到到Q1，根据约化的传递性，任何，根据约化的传递性，任何NP类问题都可约化类问题都可约化到到Q，所以，所以Q是是NP难度的。难度的。l如果进一步表明如果进一步表明Q本身是本身是NP类的，则问题类的，则问题Q是是NP完全的。完全的。l斯蒂芬斯蒂芬库克（库克（Steven CookSteven Cook）于）于19711971年证明了第一年证明了第一个个NPNP
10、完全问题，称为完全问题，称为CookCook定理。定理。CookCook定理表明可满定理表明可满足性问题是足性问题是NPNP完全的。完全的。CNFCNF可满足性问题也被证明是可满足性问题也被证明是NPNP完全的。自从完全的。自从CookCook证明了可满足性问题是证明了可满足性问题是NPNP完全完全的之后，迄今为止至少有的之后，迄今为止至少有300300多个问题被证明是多个问题被证明是NPNP难难度问题，但尚未证明其中任何一个是属于度问题，但尚未证明其中任何一个是属于P P的。的。（CookCook定理）可满足性问题在定理）可满足性问题在P P中，当且中，当且仅当仅当P=NPP=NP。CNF
11、CNF可满足性问题是可满足性问题是NPNP完全的。完全的。l证明一个问题证明一个问题Q是是NP难度（或难度（或NP完全）问题的完全）问题的具体步骤如下：具体步骤如下：（1）选择一个已知其具有）选择一个已知其具有NP难度的问题难度的问题Q1；（2）证明能够从）证明能够从Q1的一个实例的一个实例I1，在多项式时间，在多项式时间内构造内构造Q的一个实例的一个实例I；（3）证明能够在多项式时间内从）证明能够在多项式时间内从I的解确定的解确定I1的解。的解。（4）从（）从（2）和（）和（3）可知，）可知，Q1Q；（5）由（）由（1）和（）和（4）及约化的传递性得出所有）及约化的传递性得出所有NP类问题均
12、可约化到类问题均可约化到Q，所以，所以Q是是NP难度的；难度的；（6）如果）如果Q是是NP类问题，则类问题，则Q是是NP完全的。完全的。l第一步：以任意给定的第一步：以任意给定的CNFCNF公式公式F F为输入，构造一为输入，构造一个相应的无向图个相应的无向图G G，并且这种构造能够在多项式时间，并且这种构造能够在多项式时间内完成。内完成。l令令l是一个是一个CNF形式的命题公式，形式的命题公式，xi，1 i n，是，是F中的中的变量。由变量。由F生成一个无向图生成一个无向图G=(V,E)的方法为：的方法为：V=|是 子 句是 子 句 Ci的 一 个 文 字的 一 个 文 字 ，E=(,)|i
13、 j且且 。iki1CF 可满足性问题实例可满足性问题实例 F F：最大集团实例最大集团实例G=(V,E):G=(V,E):V=V=|,i|是子句是子句 C Ci i 的一个文字的一个文字，E=(E=(,)|i,j)|i j j且且 h21ik21iki1aaaCCCCCF l 第二步：如果能够证明第二步：如果能够证明F F可满足，当且仅当可满足，当且仅当G G有一有一个规模至少为个规模至少为k k的集团，那么，便证明了的集团，那么，便证明了CNFCNF可满足可满足性问题可以约化到最大集团判定问题。性问题可以约化到最大集团判定问题。l分两方面证明此结论分两方面证明此结论:l 一方面，若一方面，
14、若F F是可满足的，则必定存在对是可满足的，则必定存在对n n个布尔个布尔变量的一种赋值，使得每个子句变量的一种赋值，使得每个子句C Ci i中至少有一个文中至少有一个文字为真。字为真。l 另一方面，若另一方面，若G G有一个规模至少为有一个规模至少为k k的集团的集团GG（S S，EE），），设设S=S=,2,k是是集团的顶点集合，则必有集团的顶点集合，则必有 i i ，i i j j，若不然，则，若不然，则顶点顶点 i和和 j之间没有边，之间没有边，S S不是集团。不是集团。j 设有命题公式设有命题公式F F，)xxx()xxx(CCF32321211 图图G(V.E)有大小为有大小为2的
15、集团，的集团，F是可满足是可满足的（可令的（可令x1true，x2false）（顶点覆盖判定问题）对于无向图（顶点覆盖判定问题）对于无向图G(V,E)，集合，集合S V，如果，如果E中所有边都至少有一个顶中所有边都至少有一个顶点在点在S中，则称中，则称S是图是图G的一个顶点覆盖。覆盖的规的一个顶点覆盖。覆盖的规模是模是S中顶点的数目中顶点的数目|S|。指求图指求图G的最小的最小规模的顶点覆盖，而规模的顶点覆盖，而确定图确定图G是否存在规模至多为是否存在规模至多为k的顶点覆盖。的顶点覆盖。l对于图中所示的无向图对于图中所示的无向图G，S1=1，3和和S2=0，2，4分别是图分别是图G的顶点覆盖，
16、的顶点覆盖，S1是最小覆盖，其规模是最小覆盖，其规模为为2。最大集团判定问题最大集团判定问题顶点覆盖判定问顶点覆盖判定问题。题。：分两步证明这一结论。分两步证明这一结论。l第一步：以最大集团判定问题的任一实例第一步：以最大集团判定问题的任一实例(G，k)，G=(V，E)，k为正整数，来构造一个顶点覆盖判定为正整数，来构造一个顶点覆盖判定问题的实例问题的实例(G，n-k)，G=(V，)，n=|V|，l =(u,v)|u V,v V且（且（u,v）E。EEl第二步：分两方面证明第二步：分两方面证明“图图G有一个规模至少为有一个规模至少为k的集团，当且仅当图的集团，当且仅当图G有一个规模至多为有一个
17、规模至多为n k的结的结点覆盖。点覆盖。”l一方面，先证明：若图一方面，先证明：若图G有一个规模至少为有一个规模至少为k的集的集团团S，则图，则图G有一个规模至多为有一个规模至多为n k的结点覆盖的结点覆盖S，SV S。l反证法反证法：若：若G不能被不能被S中的顶点所覆盖，则必定中的顶点所覆盖，则必定存在边存在边(u,v)，顶点，顶点u和和v均不在均不在S 中，而在中，而在S中。中。这与这与S是图是图G的一个集团相矛盾。所以，的一个集团相矛盾。所以，S必定是必定是图图G的顶点覆盖。并且若的顶点覆盖。并且若|S|k，则，则|S|n k。El另一方面，需证明：若另一方面，需证明：若GG有一个规模至
18、多为有一个规模至多为n n k k的结点覆盖的结点覆盖SS，则，则G G有一个规模至少为有一个规模至少为k k的集团的集团S S，S=VS=V SS。反证法：反证法：若若S不是完全图，则不是完全图，则S中至少有一对顶点中至少有一对顶点u S，v S之间缺少边，该边（之间缺少边，该边（u,v）应属于）应属于 ，即，即S未覆盖此边。这与未覆盖此边。这与S是是G的顶点覆盖相矛盾。因的顶点覆盖相矛盾。因此，此，S必为完全图。若必为完全图。若|S|n k，则，则|S|k。El 可满足性的若干结果可满足性的若干结果l 是可满足的，当且仅当公式是可满足的，当且仅当公式 f=(y1y2)(y2)(y1 )()
19、是可满足的。其中，是可满足的。其中，是公式，是公式，y1和和y2是是变量。由于变量。由于y1 ，y2 ，y1y2，y2,y1 和和 不同时为不同时为真。所以，真。所以，是可满足的，当且仅当公式是可满足的，当且仅当公式f是是可满足的。可满足的。2y1y1y2y1y2y1y1y2y2yl 1 2是可满足的，当且仅当公式是可满足的，当且仅当公式 f=(1 2y)(1 2 )是可满足的。是可满足的。由于由于y ，两者之一为假。所以，两者之一为假。所以，1 2是可满足的，当且仅当公式是可满足的，当且仅当公式f是可满足的。是可满足的。yylf1f2是可满足的，当且仅当公式是可满足的，当且仅当公式 f=(f
20、1y)(f2 )是可满足的，是可满足的，f1和和f2是公式，是公式，y是变量，并是变量，并且不出现在且不出现在f1和和f2中。中。若若f1f2是可满足的，则必有是可满足的，则必有f1或或f2为真。若为真。若f1为真，可令为真，可令y为假，则为假，则f 可满足；否则，若可满足；否则，若f2为真，可令为真，可令y为真，则为真，则f可满足。可满足。若若f是可满足的，因为是可满足的，因为y ，若，若y为真，则必为真，则必有有f2为真，若为真，若y为假，则必有为假，则必有f1为真。即无论为真。即无论y为何值，只有为何值，只有f1f2为真时，为真时，f 才为真。才为真。yy CNF可满足性可满足性3元元C
21、NF可满足性。可满足性。l 3元元CNF可满足性可满足性着色数判定问题。着色数判定问题。：仍然分两步证明这一结论。仍然分两步证明这一结论。l第一步：以第一步：以3 3元元CNFCNF可满足性问题的任意一个实例可满足性问题的任意一个实例公式公式F F为输入，构造一个着色数判定问题的实例为输入，构造一个着色数判定问题的实例(G(G，k)k)，其中，其中G=(V,E)G=(V,E)为无向图，为无向图，k k为正整数。为正整数。l第二步：从两方面证明第二步：从两方面证明“3 3元元CNFCNF公式公式F F是可满足的，是可满足的，当且仅当图当且仅当图G G是是n+1n+1可着色的。可着色的。”是是辅辅
22、助助顶顶点点。其其中中，令令元元L L上上的的3 3 是是 ，设设文文字字的的集集合合构构造造图图从从n21n21r21n21n21r21n21n21y,.,y,yy,.,y,y C,.,C,C x,.,x,x x,.,x,xVCNFC,.,CCFx,.,x,x,x,.,x,xL4nLE)(V,G F 总共总共3n+k个顶点个顶点 Cx),C,x(Cx),C,(x ji),x,(y ji),x,(y ji),y,(y ni),1x,(xEjijijijijijijiii i（证明：证明：3元元CNF公式公式F是可满足的，当且仅是可满足的，当且仅当图当图G是是n+1可着色的。可着色的。（若若F F是可满足的，则图是可满足的，则图G G是是n+1n+1可着色的可着色的（若图若图G是是n+1可着色的，则可着色的，则F F是可满足的是可满足的l综上所述，可在多项式时间内从综上所述，可在多项式时间内从3元元CNF可满足性问题的任意一个实例公式可满足性问题的任意一个实例公式F，构造，构造一个图着色数问题的实例无向图一个图着色数问题的实例无向图G=(V,E)，并且并且3元元CNF公式公式F是可满足的，当且仅当是可满足的，当且仅当图图G是是n+1可着色的，所以，可着色的，所以，3元元CNF可满足可满足性性着色数判定问题，着色数判定问题是着色数判定问题，着色数判定问题是NP完全的。完全的。
