计算的复杂性第八章 NP完全性证明!10

计算的复杂性第八章 NP完全性证明!10计算的复杂性第八章 NP完全性证明!10 Email,guxf@uestc.edu.cn 2012年6月18日顾算的顾顾性第8章　NP完全性顾明, ,,哈密回路维维维 ,,三匹配维维维划分 ,维维点覆盖和 , ,,,限制法局部替法维维分量法维维维 , 99 - 2 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明　顾顾富的究人顾面顾一顾要顾明当丰研个NP完全性的顾顾Π顾～他顾的有利件是有顾顾可以利用。他顾可能在顾去已顾顾明顾顾似的条顾顾Π'的NP完全性～或者顾顾...

计算的复杂性第八章 NP完全性证明!10 Email,guxf@uestc.edu.cn 2012年6月18日顾算的顾顾性第8章　NP完全性顾明, ,,哈密回路维维维 ,,三匹配维维维划分 ,维维点覆盖和 , ,,,限制法局部替法维维分量法维维维 , 99 - 2 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明　顾顾富的究人顾面顾一顾要顾明当丰研个NP完全性的顾顾Π顾～他顾的有利件是有顾顾可以利用。他顾可能在顾去已顾顾明顾顾似的条顾顾Π'的NP完全性～或者顾顾顾顾一顾明。顾可能使他顾顾顾模个仿 Π'的NP完全性顾明顾明来Π的NP完全性～或者把Π'本身顾顾到Π顾明来Π的NP完全性。在多情下～顾顾可能容很况很易地得到了Π的NP完全性顾明。　可是～常常不到已知的顾似于找Π的NP完全顾顾。在顾顾情况研凭从数个下～究人顾可能不能直顾顾百顾已知的NP完全顾顾中挑顾出一最合适的顾顾作顾顾明的基顾。然而～顾顾仍然能顾把个个顾顾的范顾顾小到一基本顾顾的核心～顾些顾顾在顾去曾顾是有用的个很。顾然在理顾上任何已知的NP完全顾顾都能顾用顾明新顾顾的来NP完全性～但是在顾顾上某些顾顾似乎更适合用于顾明。下述六顾顾个就是顾顾最常使用的顾顾～因而我顾顾顾顾六顾顾能顾作顾初者的已个学知的NP完全顾顾的“基本核心”。 99 - 3 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明顾例,有顾的顾量集合U上的子句顾C={c,c,...,c}～其中12m　　　|c|=3～1?i?m。i 　顾,顾于U是否存在顾足C中所有子句的顾顾顾,真顾例,集合M?W×X×Y～顾里W,X和Y是三不相交个的集合～　　　　且有相同的元素个数q。　顾,M是否包含一匹配～是否有子集个即M’?M使 99 - 4 顾子科技大顾算机院顾小学学丰12,6,18得　　　|M|’,q且M'中任何元素的任何坐顾都不两个相同, 顾算的顾顾性第8章　NP完全性顾明顾例,顾G=(V,E)和正整数k?|v|。　顾,G是否有大小不超顾k的顾点覆盖～是否有子即集　　 V’? V使得|V’|?k且顾每一顾并条 (u,v)?E～u 　　和v中至少有一于个属V', 顾例,顾G=(V,E)和正整数J?|V|。　顾,G是否包含大小不小于J的顾～是否有子集即 V’?V～　　　使得|V’|?J且并V’中每顾点都由两个E中的 99 - 5 顾子科技大顾算机院顾小学学丰12,6,18一条顾顾接着。顾算的顾顾性第8章　NP完全性顾明顾例,顾G=(V,E)。　顾,G是否包含一哈密顾回路～是否有条即G的顾点排列次序使得(v,v)?E和12nn1 (v,v)?E～Ii+1 1?i,n,顾里n=|V|。顾例,有顾集合A以及每一个a?A的“大 +小”S(a)?Z。 s(a)=S(a) 顾,是否有子集A'?A使得, a?A'a?A?A' 99 - 6 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明我顾顾明顾六顾顾是将从个NP完全的顾始～顾述顾明NP完全性的方法～且在合适的顾候指出顾些顾顾的顾顾～顾的并它NP完全性或多或少可以直接地顾些基本顾顾的从NP完全性得到。第一顾顾顾顾可顾足性顾始～因顾到顾在顾止我顾只知道顾顾个将从一“已知的”个NP完全顾顾。然而在顾行顾六顾明的顾程中～个我顾已知的NP完全顾顾不地增加～且在顾明顾顾会断并Π的NP完全性顾可以利用所有在Π之前顾明了NP完全性的顾顾。顾8-1顾明我顾把顾顾顾顾到顾六基本顾顾中的每一。如果把一哪个个个个另个画个从个个顾顾顾顾到一顾顾～顾里就一箭顾第一顾顾指向第二顾顾。使他的顾序和我顾的一顾精顾顾～顾了顾明某些一般性的顾即当明方法～我顾有顾顾是修改或替顾了原的顾顾。来 99 - 7 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明可顾足性 3SAT 3DM VC 划分顾 HC 顾8-1　在顾明六基本顾顾的个NP完全性中使用的顾顾的顾序顾 99 - 8 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明　三元可顾足性顾顾是可顾足性的一顾限制形式～在顾顾顾中所有顾例个都是每一子句恰好有三文字。顾顾顾顾的顾使成顾在顾明其他顾顾个个构它的NP完全性中用得最泛的顾顾之一。广　定理8-1　三元可顾足性是NP完全的。　顾明,因顾非定型算法只需要猜想一顾顾量的顾顾顾～且在确个真并多顾式顾顾顾顾顾顾顾顾顾顾是否顾足所有顾定的三文字子句～所以容易看内个真到3SAT?NP。　我顾把SAT顾顾到3SAT。顾U={u,u,...,u}是一顾量集合～个12n C={c,c,...,c}是一子句顾～顾顾成个它SAT的一任个意的顾例。我顾12m 要构个造一顾量集合U'上的三文字子句顾C'～若使C'是可顾足的当当且顾C是可顾足的。99 - 9 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明顾了构造C'～只需要把每一子句c?C分顾替顾成原有顾量U和i 某些附加的顾量U'上的“等价的”三文字子句集合C'～其中U'jjj只在C'的子句中使用。把顾顾在一它并起～令mj U'=U?(U')j =j1 和 m C'=C'j =j1 于是只需要顾明如何从C构造C'和U'。jjj 顾C={z,z,...,z}～顾里z;1?i?k,都是从U中的顾量顾出j12ki 的文字。构造C'和U'的方法与k顾有顾。jj99 - 10 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明情况,,k=1～ 12 U'={y,y},jjj 12121212 C'={z?y?y,z?y??y,z??y?y,z??y??y}j1jj1jj1jj1jj 111情况2,U'={y},C'={z?z?y,z?z??y}jjj12j12jk=2～情况3,k=3～U'=Ф～C'={C} jjj 情况4,k,3～ i U'={y|1?i?k?3}jj 1ii+1 C'={z?z?y}?{?y?z?y|1?i?k?4}j12jji+2j k?3 ?{?y?z?z}jk?1k 99 - 11 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明　顾了顾明顾的是一顾顾～我顾确个必顾顾明～子句顾C'是可顾足的且当顾当C是可顾足的。首先假顾t,U?{T,F}是一顾足个C的顾顾顾。真我顾顾明t可以顾顾成一顾足个C'的顾顾顾真t',U'?{T,F}。因顾U'-U中的顾量分成集合U'～且每一并个U'中的顾量只出顾在于属jj C'的子句中～所以我顾只需要顾每一顾情分顾顾明如何把况t顾顾到j U'上去～且顾顾并t'顾足顾顾的C'中的所有子句。我顾的做法如下jj ,如果U'是在情况1或情况2下成的～构那顾t已顾顾足C'中所jj有子句～所以可以把t任意地顾顾到U'上～譬如顾～顾所有的j Y?U'～令t'(y)=T。如果U'是在情况3下成的～构那顾U'jjj是空集～且并t已顾顾足C'中唯一的子句。只剩下情况4～顾顾它j C中的一子句个{z,z,...,z}～k,3。因顾t是顾足C的顾顾顾真12k99 - 12 顾子科技大顾算机院顾小学学丰12,6,18～所以一定有一最小的整个数p使得文字z在t下取真顾。如果p p等于1或2～顾算的顾顾性第8章　NP完全性顾明 i那顾令t’(y)=F～1?i?k-3～如果p等于k-1或k～那顾令j it’(y)=F～1?i?k-3～否顾当1?i?p-2顾～令j iit‘(y)=T～当p-1?i?k-3顾～令t’(y)=F。容易顾顾顾顾顾取顾jj 能保顾顾足c’中的所有子句。所以t’顾足C’中的所有子句。j 反之～如果t’是C’的一顾足的顾顾顾～容易顾顾个真t’限制在U中的顾量上一定是一顾足个C的顾顾顾。于是真C‘是可顾足的当且顾当C是可顾足的。顾了看出能顾在多顾式顾顾完成顾顾顾～只要顾顾内个C'中三文字子句的不超顾个数mn的一多顾式就足顾了。因个此～2SAT顾例的顾模不超顾SAT顾例的顾模的一多顾式个数构函。又因顾造本身 99 - 13的全部顾顾是顾顾的～大很个会家要顾顾顾是一多顾式顾顾不有什顾困顾。顾子科技大顾算机院顾小学学丰12,6,18 ? 顾算的顾顾性第8章　NP完全性顾明 3SAT的顾顾有限制的顾使在构它NP完全性顾明中比SAT有用得多。任何以SAT顾基顾的顾明;除我顾顾顾顾出的顾一,都可以个立即顾化成以3SAT顾基顾的顾明～甚至不需要改顾顾顾。事顾上～使子句具有同顾大小的顾准化常常可以顾化所要构从造的顾顾～而使得它找很顾比顾容易地到。此外～顾些子句都小～因而可以使用那些不能顾理含有顾大子句的顾例的顾顾。顾使我顾想到～如果能顾顾明顾似的二元可顾足性顾顾在顾顾顾中每子句恰好有二文字是——个个个—— NP完全的～就更加方便了。但是～2SAT可以用“分解”技顾在不超顾顾定顾例中顾量和子句数数内决乘顾的多顾式顾顾解～因此2SAT属于P。 99 - 14 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明三顾匹配顾顾是顾典的“婚姻顾顾”的推广～“婚姻顾顾”的提法是,有几个几个双未婚男子和未婚女子以及一顾列出所有方都表示愿意顾合在一起的一顾顾男子和女子的表格～顾是否能安排顾几个与并婚姻使得每人都自己愿意接受的配偶顾婚且不出顾重婚,顾似地～在三顾匹配顾顾中～集合W,X和Y顾顾于三不个同的性顾～而M中的每一三元顾顾顾一顾顾三成顾都能接个个受的三方婚姻。和前一顾顾顾似～个内普通的婚姻顾顾可以在多顾式顾顾解决～而3DM是NP完全的。　定理8-2　三顾匹配是NP完全的。 99 - 15 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明　顾明,因顾非定型算法只需要猜顾一由确个M中q=|W|=|X|=|Y|三元顾顾成的子集～且在多顾式顾顾顾顾个并内出是否是任意的猜想的三元顾都有一相同的坐两个没个顾～所以容易看出3DM?NP。　我顾要把3SAT顾顾到3DM。顾U={u,u,...,u}和12nC={c,c,...,c}分顾是3SAT的任意一顾例中的顾量集个12m 合和子句顾。我顾必顾构造互不相交的集合W,X和Y;|W|=|X|=|Y|,和集合M?W×X×Y～且使M包含一匹配且顾个当当C是可顾足的。　按照顾想的功能,“顾真安排和扇出”～“顾足性顾顾”和“顾料堆”～把有序三元顾集合M分成三顾。划99 - 16 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明每一顾个真个安排和扇出分量顾顾一顾量u?U～的它构与造C中子句的顾数m有顾～当m=4顾的顾顾构造示于顾8-2。一般地～顾顾于顾量u的顾真内安排和扇出分量包含“部”元素a[j]?X和iib[j]?Y～1?j?m及“外部”元素u[j]～，uii [j]?W～1?j?m。“内部”元素a[j]和b[j]不出顾在顾分量个iii 以外的任何三元顾中～而“外部"元素u[j]～，u[j]会出顾在其i i t它个两个三元顾中。顾成顾分量的三元顾可以分成集合,T={(?u[j],a[j],b[j]):1?j?m)}iiii f T={(u[j],a[j+1],b[j]):1?j是一哈密顾回路顾条12n ～我顾称(v,v)～1?i,n和(v,v)是在顾回路“里”的顾条ii+1n1 。 99 - 34 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明 8-4 　顾明,因顾非定型算法只需要猜想一顾点的排列次序～确个并且在多顾式顾顾顾顾所要的顾是否都于顾定顾的顾集合～所以容易看内属出HC?NP。　我顾把顾点覆盖顾顾到HC。顾顾G=(V,E)和正整数K?|V|是VC的一顾例。要个构个造一顾G'=(V',E')使得G'有一哈密顾回条路且顾当当G有一大小不超顾个K的顾点覆盖。可以再次按照用顾顾顾顾把分量顾接在一起的方式来构考顾我顾的造。首先～顾G'有K个“顾顾子”顾点a,a,...,a～用顾顾它从G的顾12k 99 - 35 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明点集V中挑顾出K个顾点。其次～顾E中的(u,e,1) (v,e,1) 每一顾条G‘包含一“覆盖顾顾”分量～用个 (u,e,2) (v,e,2) 它来条个保顾顾一顾至少有一端点在挑顾出的 (u,e,3) (v,e,3) K个顾点之中。在顾8-4中顾明了顾于 (u,e,4) (v,e,4) e=(u,v)?E的顾顾分量。有它12顾点个 V'={(u,e,i)～(v,e,i)|1?i?6}e(u,e,5) (v,e,5) 和14顾条 (u,e,6) (v,e,6) 顾8-4 在顾点覆盖到哈E'={((u,e,i),(u,e,i+1))～e 密顾的顾顾中使用的顾于　　((v,e,i),(v,e,i+1))|1?i?5} 顾e=(u,v)的覆盖顾顾分 ?{((u,e,3),(v,e,1))～((v,e,3), (u,e,1))} 99 - 36 顾子科技大顾算机院顾小学学丰12,6,18?{((u,e,6),(v,e,4))～((v,e,6), (u,e,4))} 顾算的顾顾性第8章　NP完全性顾明在完成后的构个造中～顾顾点覆盖顾顾分量中只有(u,e,1)～(v,e,1)～(u,e,6)和(v,e,6)可以包含在其它添加的顾中。于是～大家可以容易地顾顾～G‘中任一哈密顾回路恰好条按照顾8-5所示的三顾形式中的一顾顾顾E'e中的顾。例如～如果回路在(u,e,1)“顾入”顾分量～个那顾一定在(u,e,6)“退出”顾分量且或者顾顾分量个并 (u,e,1) (u,e,1) (v,e,1) (v,e,1) 中所有的12顾点～或者恰好顾顾个6顾点个(u,e,i)～1?i?6。 (u,e,6) (u,e,6) (v,e,6) (v,e,6) (a) (b) (c) 顾8-5　一哈密顾回路条通顾顾于顾e=(u,v)的覆盖顾顾分量的三顾可能的形式～分顾顾顾下述三顾情,况(a)u于顾覆盖但属个v不于顾覆盖属个～ (b)u和v都于顾覆盖属个～(c)u不于顾覆盖但属个v于顾覆盖属个 99 - 37 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明在整个构来造中添加的顾用顾接一顾覆盖顾顾分量～或者顾接一覆盖顾顾分量一顾顾子顾点。顾每一顾点个与个个 v?V～把人射到v的顾(任意地)排列成e,e,...,e～顾里deg(v)表示v在G中的度数v[1]v[2][deg(v)] ～人即射到v的顾。所有顾顾于顾些;以数v顾端点的,顾的覆盖顾顾分量用下述顾接顾顾接在一起, E'={((v,e,6)～(v,e,1))|1?i,deg(v)}vv[i]v[i+1] 　如顾8-6所示～成它构G'中恰好包含所有形如(x,y,z)的顾点的唯一路～其中径x=v。 99 - 38 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明 (v,e,1) v[1] ,6) v[1](v,e ,1) v[2](v,e ,6) v[2](v,e(v,e,6) v[3] ,1) v[3](v,e(v,e,1) v[deg(v)] ,6) v[deg(v)](v,e 顾8-6　顾接顾顾于E中以v顾端点的顾的所有覆盖顾顾分量的路径 99 - 39 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明　　最后再用顾接顾把每一顾顾的路的第一和最条径个个后一顾点与个每一顾顾子顾点a, a,...,a顾接起来。顾些顾顾定如下,12k E''={(a,(v,e,1)),(a,(v,e,1))|1?i?K,v?V}iv[1]iv[deg(v)] 顾G'=(V',E')构造好之后～ V'={a|1?i?K}?V'ie, e?E E'=E'?V'?E"ev,, e?Ev?V 不顾看到能顾在多顾式顾顾内从G和K造构出G'。　　我顾要顾明G'有哈密顾回路且顾当当G有大小不超顾K的顾点覆盖。假顾是G'的一哈密顾回路～顾里条n=|12n V'|。考顾顾回路中任条从意一段集合{a,a,...,a}中的一顾点个12k99 - 40 顾子科技大顾算机院顾小学学丰12,6,18到集合顾算的顾顾性第8章　NP完全性顾明{a1,a2,...,a}中的一顾点～而中顾不顾顾顾顾顾点的路。个径根据前k 面述的哈密顾回路顾顾一覆盖顾顾分量的可能方式～顾一叙个段路径所顾顾的覆盖顾顾分量一定恰好顾顾于E中人射到某一顾点个v?V的顾～以顾8-5中的模式(a),(b),(c)中的一顾～顾顾每一个顾顾的覆盖顾顾分量～且不顾顾其覆盖顾顾分量的顾点。于是并它 {a,a,...,a}中的K个条顾点把顾哈密顾回路分成K段路～每径12k 一段路顾顾一不同的顾点径个v?V。因顾顾哈密顾回路～条必顾包含每一覆盖顾顾分量的所有顾点～而且只有顾顾于顾个e?E的一个端点的那一段路径才可能顾顾顾于e的覆盖顾顾分量的顾点～所以E的每一顾一定至少有一条个端点在顾K个来挑顾出的顾点中。因此～顾K个顾点顾成的集合是G的一顾点覆盖。个 99 - 41 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明**　　相反地～假顾V?V是G的一顾点覆盖且个|V|?K。我顾 **可以假顾|V|=K～因顾在V中增加一些V的顾点之后～仍然是 *一顾点覆盖。顾个V中的元素顾作v,v,...,v。把下面述的一叙12k 些顾顾顾G'的哈密顾回路。顾于每一顾条e=(u,v)?E～根据 *{u,v}?V等于{u}～{u,v}～或{v}～顾顾的覆盖顾顾分量中分从 *顾顾顾顾8-5(a),(b)或(c)中所指明的顾。因顾V是G的一顾点覆个盖～所以顾三顾可能中一定有一顾可能成立。其次～顾1?i?K顾顾E'中所有的顾。最后～顾顾顾vi (a～(v,e,1))～1?i?Kiivi[1] (a～(v,e,1))～1?i,Ki+1ivi[deg(vi)] 以及 (a,(v,e,6))1kvk[deg(vk)] 99 - 42　　顾大家自己顾顾顾些顾顾顾成确构G'的一哈密顾回路。条? 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明　我顾顾哈密顾回路的顾顾几个很也有顾趣。哈密顾通路顾顾和HC相同～只是不再要求序列中第一顾点和最个个条后一顾点由一顾顾接着。点之顾的哈密顾两通路和哈密顾通路基本相同～只是把两个顾定顾点u和v作顾顾例的一部分～且顾并G是否有从u顾始到v顾束的哈密顾通路。顾顾才用于HC的顾顾作顾顾的修改后就能顾用顾明顾顾顾都是来两个NP完全的。我顾顾顾地修改最后所顾得的顾G'如下,增加三新顾点个a,a,a以及顾两条(a,a)和0k+1k+201(a,a)～且用并(a,(v,e,6))代替形如(a,k+1k+2k+1v[deg(v)]1(v,e,6))的每一顾。在点之顾的哈密顾条两两个通路中指v[deg(v)] 定的顾点是a和a。99 - 430k+2 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明　如果我顾用有向顾代替无向顾G～用有向的哈密顾回路或通路代替无向的哈密顾回路或通路～上述三顾哈密顾顾顾仍然是NP完全的。有向顾G=(V,A)由顾点集V和顾点的有序顾;叫做孤,集合A顾成。有向顾G=(V,A)中的哈密顾通路是V的一排列次序个使得顾12n 于1?i,n～有?A～其中n=|V|。一哈条ii+1 密顾回路顾要增加一要个求?A。把顾定的无向顾n1 中的每一顾条(u,v)替顾成两条和～顾三顾无向的哈密顾顾顾都可以顾顾到顾顾的有向的哈密顾顾顾。顾顾上～无向的形式只是顾顾顾的有向顾顾的它况特殊情。 99 - 44 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明　顾一顾我顾考顾六基本的个NP完全顾顾中的最后一顾顾。顾于顾个明含有字例如顾数参数————度、重量、成本、生顾能力等的顾顾的NP完全性～它特顾有用。　　顾明,因顾非定型算法只需要猜想确A的一子集个A'～并且在多顾式顾顾顾顾内A'中元素的大小之和是否等于A-A'中元素的大小之和～所以容易看出分?划NP。　我顾把3DM顾顾到分。顾集合划W,X,Y和M?W×X×Y是3DM的任意一顾例～其中个|W|=|X|=|Y|=q。顾顾些集合的元 99 - 45 顾子科技大顾算机院顾小学学丰素顾作,12,6,18 顾算的顾顾性第8章　NP完全性顾明 W={w,w,...,w}12q X={x,x,...,x}12q Y={y,y,...,y}12q 以及 M={m,m,...,m}12k 顾里k=|M|。我顾必顾构个造一集合A～以及每一个a?A的大 +小s(a)?Z～且使得A包含一子集个A'～顾足件条 s(a)=s(a) a?A'a?A?A' 当当且顾M包含一匹配。个集合A一共有k+2元素～分个两构步成。A的前k元个素是{a|1?i 99 - 46 顾子科技大顾算机院顾小学学丰i?k}～顾里元素a和三元顾m?M相顾顾。a的大小s(a)用二顾12,6,18iiii制顾算的顾顾性第8章　NP完全性顾明顾出～我顾把顾二顾制;是一个数它串0和1,分成3q“段”～每一段有p=?log(k+1)?位～顾有W×X×Y中的一元素～如顾个8-2 7所示。 … … … w … w x x … x y y … y 12q12q12qw 顾8-7　在从3DM到分的顾顾中使用的划3q“段”的顾示～每一段包含s(a)的二顾制表示的p=?log(k+1)?位2 　　顾于顾一部分构造必顾看到的一件重要事情是,如果把{a|i1?i s(a)的顾程?k}的所有元素在任意一段中的容加内来起～其和不可能超顾a?A'中不出顾一会从段到下一段的顾位。因此～如果令 k? 99 - 47P顾子科技大顾算机院顾小学学丰12,6,182-l。因而～顾于任何子集A'?{a|1?i?k}～在顾算i 顾算的顾顾性第8章　NP完全性顾 3q?1明 pj B=2 j0= ;顾的二顾制个数表示在每一段的最右一位顾1,～那顾子集A'? {a|1?i?k}顾足 i s(a)=B a?A' 当当且顾M'={m|a?A'}是M的一匹配。个ii 构造的最后一步是顾定A的最后两个它元素。顾顾作b和1 kkb并且具有如下定顾的大小2 s(b)=2s(a)?Bs(b)=s(a)+B1i2i ==i1i1 它顾都能顾用不超顾(3pq+1)位的二顾制顾出～因而可以在顾定数的3DM顾例的顾模的多顾式顾顾成。内构 99 - 48 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明顾在假顾有一子集个A'?A使得 s(a)=s(a) a?A'a?A?A' k 那顾顾和式一定都两个等于～且并A'和A,A'中有一2s(a) i =个包i1 含b～但不包含b。于是顾集合中个剩余的元素顾成{a|12i1?i?k}的一大小之和个等于B的子集～因而根据前面的注顾～顾子集顾顾个M中的一匹配个M'。相反地～如果M'?M是一个匹配～那顾集合{b}?{a|m?M'}顾成所需要的顾于分的顾例划1ii P 3DM分～而定理得顾。划从? M的子集A'。因此～ 99 - 49 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明 NP完全性的顾明方法和NP完全顾顾的本身一顾是非常泛的广～因而我顾不能指望在顾里顾明所有顾些方法。然而～有顾顾常顾到的几顾明顾型～顾能顾它个启框来提供一有顾性的架～用判定如何去顾明一新顾顾是个NP完全的。我顾把顾顾顾明顾型几叫做, 99 - 50 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明在顾一顾我顾将来几主要通顾例子顾明顾顾顾明顾型。企顾顾出它确将顾的明定顾是十分愚蠢的。顾多顾明可以被任意地解顾成顾三顾顾型中的任一顾～顾有一些顾明方法是顾顾某个特殊顾顾的～所以不可能用有限的顾顾型几自然地把所有的顾明方法都包括顾。因来几此～我顾告顾大家不要把顾顾顾型顾成顾所有NP完全性顾明的一顾分顾方法。而可顾～我顾宁唯一的意顾是把我顾已顾顾顾的考顾NP完全性顾明的顾方法几既解顾得有直顾地感染力又有建顾性。顾了顾明起顾～我顾在所有的顾明中将属省略了顾定顾顾于NP的顾顾。容易看出所考顾的每一顾顾都能顾用非定型算个确法在多顾式顾顾内决解～而且如果需要的顾～大家不顾提供顾顾一个算法。 99 - 51 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明　限制法顾明是顾三顾顾型中最顾顾、也差不多是最顾常用的一顾顾型。用限制法顾明顾定顾顾Π?NP的NP完全性就是顾明Π包含一已知的个NP完全顾顾Π'作顾的一顾它况特殊情。顾顾一个顾明的核心在于顾Π的顾例顾定一些附加限制使的所得到的顾顾等同于Π'～我顾不要并个求顾受到限制的顾顾恰好就是已知的NP完全顾顾～而只要求在顾的顾例之顾有一“顾然的”它个、能顾保持“是”“否”与答案不顾的一一顾顾。顾一一顾顾顾出所需要个——它的从Π'到Π的顾顾——通常是非常明顾的～以致于不需要明顾的顾出。来 99 - 52 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明　我顾已顾看到顾顾顾明顾型的例子。在几个8.1.2顾中～三元集合构当成的恰覆盖顾顾的NP完全性顾明是通顾限制的顾例是由集合它 W的一元素～集合个X的一元素以及集合个Y的一元素顾成个的三元集合～而得到一从个等同于3DM顾顾的顾顾～顾里W,X和Y是具有相同基的不相交的集合。在数8.1.4顾中～有向的哈密顾回路顾顾的NP完全性顾明是通顾限制的顾例是一每一它个条弧和其反向的弧同顾出顾的有向顾～而得到一从个等同于无向的哈密顾回路顾顾的顾顾。　因此可以顾顾限制法顾明顾了一顾不同于顾体准的NP完全性顾明的顾察事物的方式。我顾不是去顾顾顾顾把一已知的个NP完全顾顾顾顾到目顾顾顾的方法～而是考顾目顾顾顾本身～努力去掉它的“非本顾”方面直到顾得一已知的个NP完全顾顾顾止。 99 - 53 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明　顾例,集合S的子集顾C和正整数K。顾,C是否包含S的大小不超顾K的覆盖～即是否包 c=S 含一子集个C’?C～|C’|?K～使得, c?C' , 顾明,由只允顾顾例中所有的c?C有|c|=3以及K,|S|/3～把顾顾顾限制于个X3C。 99 - 54 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明　顾例,集合S的子集顾C和正整数K。　　顾,S是否包含C的大小不超顾K的顾中集～即是否有一子集个S’?S～|S’|?K～使得S’至少　　顾明,由只允顾顾例中所有的cC?有|c|=2～把顾个包含C中每一子集中的一元素,个个顾顾限制于VC。 99 - 55 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明　顾例,两个顾G=(V,E)和H=(V,E)。1122 　顾,G是否包含同于构H的子顾～是否有子集即 V?V和子集E?E使得|V|=|V|～|E|112=|E|～并2 且存在一一顾一的个数函f,V?V顾足2 　　顾明,由只允顾顾例中的H是完全顾～即E包含所2 (u,v)?E当当且顾(f(u),f(v))?E。2 有顾接V中点的顾～把顾顾顾限制于顾。两个2 99 - 56 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明　顾例,顾G=(V,E)和正整数K?|V|-1。　　顾,G是否有一所有顾点的棵数度不超顾K的生成顾～是否有一子集即个E’?E使得|E’|?|V|- 1～顾G'=(V,E’)是顾通的～且并V中每一　顾明,由只允顾顾例中的K,2～把顾顾顾限制于哈个个顾密顾通路顾顾。 99 - 57 点至多包含在E'的K条顾中, 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明　顾例,有向顾G=(V,A)和正整数K?|A|。顾,是否有一有向顾个G’=(V,A’)～若使得A’?A～|A’| ?K～且顾于并V中的每一顾顾点u和v～G‘包含一条从u　顾明,由只允顾顾例中的G是强顾通的且并K=|V|～把顾顾顾限个到v的有向路顾且顾当当G包含一条从u到v的有向制于有向的哈密顾回路顾顾。顾里所顾强顾通是指包含每一顾点从个路,径u到每一顾点个v的有向路。径注意顾顾上是把顾顾限制于顾于强顾通顾的有向的哈密顾回路顾顾。但是根据我顾顾出的顾于HC和有向的HC的构即个造～立得到顾顾顾的NP完全性。 99 - 58 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明　顾例,有顾集合U～每一个u?U的“大小”s(u)和“价 ++ 顾”v(u)?Z～以及大小的顾束B?Z和价顾目 s(u)?Bv(u)?K且,+ 顾K?Z。 u?U'u?U' 　　顾,是否有一子集个U'?U使得　顾明,由只允顾顾例中所有的u?U有s(u),v(u)～ 11 以及B=s(u)K=s(u)～～把顾顾顾限制于分。个划 22u?Uu?U 99 - 59 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明顾例,有顾的“任顾”集A～每一个a?A的“顾度” L(a)?Z+～以及“顾理机”的数目m?Z+和“截止顾顾”D?Z+。 max{L(a)|1?i?m}?D 顾,是否能把A分成划m不相交的集合个 a?Ai 1 A=A?A?...D=L(a)12　顾明,由只允顾顾例中m=2并～把顾顾个 2a?A ?A使得且m顾限制成分顾顾。划 99 - 60 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明最后顾要指出～我顾顾顾在要顾顾的几个NP完全性的顾明方法中～限制法顾明最适合于那些除知道六个基本顾顾及其顾形之外～顾知道各顾各顾的NP完全顾顾的人。顾顾中提出的顾多顾顾只不顾是我顾已知的NP完全顾顾的更顾顾的形式～因此如果有能力顾顾出顾一点～常常可以用限制法很快地顾明出NP完全性。 99 - 61 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明在采用局部替顾法的顾明中～要用顾准的顾明格式把顾顾顾清楚是十分不容易的～但是相顾地顾顾些顾顾仍然不来太顾顾。我顾所要做的一切是顾顾已知的NP完全顾顾顾例的某方面作顾基本顾元～个然后用不同的顾顾一地替顾每一基本顾元～得到构个目顾顾顾的顾顾顾例。8.1.1顾中从SAT到3SAT的顾顾就于顾顾顾型。在属个那顾顾中～SAT顾例的基本顾元是子句～每一子句都个个按照同一一般的顾顾替顾成一子句顾。个必顾看到的顾顾一点是每一替顾顾顾成个构顾的构局部修改。除去反映原顾例的不改顾的来部分～顾些替顾在本顾上是相互立独的。　　下面的判定顾顾顾顾于顾算一顾顾定的初等顾乘顾所需乘法次数的小极运化顾顾～顾里假定乘法算是可顾合和可交顾的。 99 - 62 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明顾例,有顾集合A的子集顾C和正整数J 　顾,是否存在j?J算的序列个并运 111222jjj 顾里x和y或者是{a};a?A,或者是ziik ;k,i～使得顾于1?i?j～x和y不相交～且顾于每一并ii 99 - 63个子顾子科技大顾算机院顾小学学丰12,6,18 集c?C顾有某个z;1?i?j,等于c,i 顾算的顾顾性第8章　NP完全性顾明定理8-6 整顾算是体NP完全的。　　顾明,我顾把顾点覆盖顾顾到整顾算。顾顾体G=(V,E)和正整数K?|V|成构VC的任意一顾例。个　　VC顾例的基本顾元是G的顾。顾a是不在V的某新元内个0 素。局部替顾法把每一顾条(u,v)?E替顾成子集{a,u,v }?C。0整顾算的顾例由下式顾定,体 A=V?{a}0 C={{a,u,v}|(u,v)?E }0 J=K+|E| 容易看到能顾在多顾式顾顾成顾顾例。我顾要顾内构个G有一大小个不超顾K的顾点覆盖且顾顾于当当C存在所要求的j;j?J,个 99 - 64运算的序列。顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明首先～假顾V‘是G的一大小不超顾个K的顾点覆盖。因顾在V’上增添一些顾点后仍然是一顾点覆盖～所以可以个假顾|V‘|=K～而不失一般性。把V’的元素顾作v,v,...,v～E的12K元素顾作e,e,...,e～顾里m=|E|。因顾V‘是一顾点覆盖～所个12m 以每一顾条e至少包含V’的一元素。于是我顾把每一顾个条e写jj成e=(u,v)～顾里r[j]是一整～且个数并1?r[j]?K。容易jjr[j] 看到下述K+|E|=J算的序列个运具有要求的所有性顾, K+11r[1]K+22r[2]mmr[m] 相反地～假顾顾于整顾算的顾体 99 - 65 顾子科技大顾算机院顾小学学丰例～S=是所求的12,6,18111222jjj j?J算的序列。我顾个运再顾一步假顾顾顾算的顾顾性第8章　NP完全性顾明于顾顾例～个S是顾顾序列中最短的一～而且在所有顾顾最个短的序列中～S包含形如z={u}?{v};u,v?V,的算的最少。运个数i 我顾首先顾明S不可能包含顾顾形式的算。运假顾S包含z={u}?{v}～u,v?V。由于(u,v)不在C中～而且S的顾度是i 最短的～所以必有(u,v)?E～且在并S中的后面一定要出顾{a,u,v}={a}?z;或z? {a},。因顾{u,v}只是C的一元个00ii0 素的子集～所以不可能在顾最个它运短的序列的任何其算中用到z。而我顾可以把顾算从两个运i z={u}?{v}和{a,u,v}={a}?zi00i 替顾成 99 - 66z={a}?{u}和{a,u,v}={v}?zi00i顾子科技大顾算机院顾小学学丰12,6,18 在不增加整序列顾个况减度的情下少了形如z={u}?{v} i ;u,v? 顾算的顾顾性第8章　NP完全性顾明V,的算运数与目～顾S的顾顾矛盾。所以S顾由顾形式的算两运 z={a}?{u};u?V,和{a,u,v}={v}?z;(u,v)?E,顾i00i 成(顾里我顾不考顾每一顾情中算顾况两个运象的相顾顾序)。因顾|C|=|E|且并C的每一成顾包含三元素～所以个个S一定恰好包含|E|个运后一顾形式的算和j-|E|?J-|E|=K个运前一顾形式的算。因此集合, V'={u?V|z={a}?{u}是S中的一算个运}i0 至多包含V中的K个并顾点～且根据C的构它造～容易顾顾一定是G的一顾点覆盖。个? 　一用另个从局部替顾法的多顾式顾顾顾顾的例子如下。顾一次三元集合成的恰覆盖出顾。构当 99 - 67 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明顾例,顾G=(V,E)～顾里|V|=3q～q是一正整个数。　顾,是否能把V分成划q不相交的三顾点集合个 V,V,12 ...,V使得顾于每一个V={v,v,v}～三qii[1]i[2]i[3] 顾条(v,v),(v,v)和(v,v)都i[1]i[2]i[1]i[3]i[2]i[3] 于属E, 99 - 68 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明　顾明,我顾把三元集合成的恰覆盖顾顾到三构当划角分。　顾集合X～|X|=3q和X的三元素子集顾C是X3C的任意一顾例。我顾要个构个造一顾G=(V～E)～|V|=3q～使得顾于G存在所要求的分～且顾划当当C包含一恰覆盖。个当　X3C顾例的基本顾元是C中的三元素子集。局部替顾法把每一子集个c={x,y,z}?C替顾成顾8-7所示的18顾的集合条iiii E。于是G=(V,E)定顾顾i|C||C| V=X?{a[j]|1?j?9}E=E,,ii ==i1i1 99 - 69 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明 a a[3] [9] ii [6] ia a[2] a[7] ii[8] aa[1] [5] ii[4] iaia y z iiix 顾8-7 在从X3C到三角划分的顾顾中顾于c={x,y,z}?C的局部iiii 替顾 99 - 70 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明注意～只有那些在于不只一属个E的顾中出顾的顾点才可能i 是集合X中的元素～顾要注意|V|=|X|+9|C|=3q+9|C|。而从q’=q+3|C|。不顾看到三角划个内分的顾顾例能顾在多顾式顾顾由X3C的顾例构来造出。如果c,c,...,c是X的一恰覆盖中的三元素子集～个当那12q 顾V的顾顾分划V=V?V?...?V由下述方法顾出。若12q' c={x,y,z}在恰覆盖中～当从与E顾顾的顾点中取iiiii {a[l],a[2],x}～{a[4],a[5],y}～{a[7],a[8],z}～iiiiiiiii {a[3],a[6],a[9]}iii 若c不在恰覆盖中～当从与E顾顾的顾点中取ii 99 - 71 顾子科技大顾算机院顾小学学丰12,6,18{a[l],a[2],a[3]}～{a[4],a[5],a[6]}～{a[7],a[8],a[9]}iiiiiiiii 顾算的顾顾性第8章　NP完全性顾明顾顾做保顾X的每一元素都恰好包含在顾分中的一个个划个 3顾点子集中。相反地～如果V=V?V?...?V是G的任意一三个12q‘ 角划从分。C中挑顾出那些使得顾于某个j(1?j?q’)～{a[3],a[6],a[9]},V的c～顾些c顾成顾顾的恰覆盖。顾大当iiiiii 家顾顾我顾构两个划造的顾分顾足我顾的要求～顾件工作是顾顾的。? 99 - 72 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明我顾顾才看到的例子两个称描述了什顾顾的顾明可以被作“顾粹的”局部替顾顾明。目顾顾例的顾完全定于顾定的顾顾顾例的顾构决构构和使用的局部替顾。在顾顾顾中增添有限的附加顾构常常是有益的～顾些附加顾构起着“顾施者”的作用～把某些附加限制强加在顾目顾顾例能顾得到答案“是”的方式上。顾于具有“顾定顾例I～是否存在X具有所要求的性顾,”形式的目顾顾顾～在II 中顾施者部分起着限制可能的X的作用～使得余下的顾顾来反I 映那些在原顾顾的顾例中可以得到的顾顾～而顾原的顾例用来运局部替顾得到的部分提供顾行顾顾顾顾的手段～且并它保顾顾具有所要求的性顾。在分的划NP完全性顾明中的元素两个b和b就起12着顾顾顾施者的作用。我顾再顾使用顾两个施者的局部替顾法顾明的例子。先考顾下述顾度顾顾。99 - 73 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明顾例,有顾的“任顾”集T～顾于每一个t?T有一整的“顾个数 + 放顾顾”r(t)?0～一“个截止顾顾”d(t)?Z以及“顾 + 度”l(t)?Z。顾,是否存在顾于T的可行顾度～是否有一即个数函σ,T? +　　　Z?{0}使得顾于每一个t?T,σ(t)?r(t)～σ(t)+l(t) ?d(t), 且如果并t‘?T-{t}～那顾或者σ(t')+l(t') ?σ(t)～或者σ(t)+l(t)?σ(t‘),;顾顾从σ(t)到 σ(t)+ l(t)之顾“顾行”任顾t,在顾顾r(t)之后才能顾 99 - 74 顾子科技大顾算机院顾小学学丰12,6,18 始顾行～在顾顾d(t)之前必顾完成～且和任何其并它它任顾t'的顾行顾顾不能重叠。, 顾算的顾顾性第8章　NP完全性顾明　顾明,我顾把分顾顾到顾顾顾。顾有顾集合划个A和顾于每一个a?A顾定的大小s(a)顾成分的任划个并意一顾例～且令B=Σs(a)。a?A 　分的顾例的基本顾元是划个各元素a?A。顾于每一个a?A的局部替顾是一顾任顾t～且有a tr(t)=0～d(t)=B+1以及l(t)=s(a)。“顾施者”是aaa ttt 一顾任顾　且有r(　)=?B/2?～d(　)=?(B+1)/2?以 99 - 75及l(　)=1。顾然能顾在多顾式顾顾由分的顾例内划构造出顾子科技大顾算机院顾小学学丰12,6,18 顾顾例。个顾算的顾顾性第8章　NP完全性顾明　　顾施者强加在可行顾度表上的限制有二顾。第一～它当保顾B是奇整顾不可能数构况划造出可行顾度表;在顾顾情下～顾于分的 tt顾例不可能存在所要求的子集,～因顾顾顾顾有r(　)=d(　)～所以不可能把　排入顾度表。于是顾在从起我顾假顾B是偶数。t 在顾顾情下～第二限制况个来提出了。因顾B是偶数～所以r t(　)=B/2～而d(　)=r(　)+1～使得任何可行顾度表都必顾 ttt 有σ(　)=B/2。顾就把可以用来安排其余任顾的顾顾分成分顾的两段～每一段的顾度顾B/2～如顾8-8所示。于是顾顾个度顾顾顾顾成 tt挑顾子集的顾顾～一些安排在　之前～而一些另安排在　之后。因顾顾两段可利用的顾顾顾共等于剩余任顾的顾顾度B～所以每一段顾顾都必顾安排顾。但是～且顾有一子集当当个A'?A使得 99 - 76 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明 B s(a)s(a) 2a?A'a?A?A' 顾能顾做到顾一点。于是顾于分的顾例存在所要划求的子集A'且顾顾于顾排序的顾顾顾例存在一可行顾当当区个度表。? BB 22 , , t BBB+1 0 +1 22 顾8-8 从划区分到顾排序的顾顾所“顾施的”顾度表 , 99 - 77 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明顾例,有顾的“可能的顾”集合断A～A的子集顾C;顾些子集表示二元“顾顾”,以及正整数J?|C|。　顾,是否有子顾C‘?C～|C’|?J使得顾于A中每一顾可能的顾断a,a～顾存在某顾顾个c?C‘使得ij |{a,a}?c|=1ij 99 - 78 顾子科技大顾算机院顾小学学丰 ;存在一顾即个区a和a的顾顾c,, 12,6,18ij 顾算的顾顾性第8章　NP完全性顾明　顾明,我顾把3DM顾顾到顾顾顾。顾集合个W,X,Y～|W|=|X|=|Y|=q和集合M?W×X×Y顾成3DM的任意一顾例。个　3DM顾例的基本顾元是M中的有序三元顾。局部替顾法把每一个m,(w,x,y)M?替顾成子集{w,x,y}C?。添加三不于个属WXY??的元素w,x,y和顾顾两个W{w?}～X{x?}作顾顾施者。00000 由 A=WXY{w???,x,y}000 C={{w,x,y}|(w,x,y)M}{W{w???}～X{x?}}00 J=q+2 　定顾了一完整的最小顾顾集的顾例。容易看到能顾在多顾式顾顾个99 - 79 顾子科技大顾算机院顾小学学丰12,6,18 内由顾定的3DM顾例构个造出顾顾例。顾算的顾顾性第8章　NP完全性顾明顾施者再一次把某些限制强加在所要求的顾例;在顾情下是顾顾况子顾C',上。首先～C'必顾包含既W?{w}又包含0X?{x}～因顾顾顾顾是两个唯一可以把y和w以及x区来顾顾顾的0000顾顾。其次～因顾w,x和y不包含在C的任何其顾顾中～所以它000 顾了把W?X?Y中的每一元素个与w,x或y区来顾顾顾～必顾把000 它个包含在某c?C'-{W?{w}～X?{x}}中。至多能包含00 J-2=q顾顾顾顾。个又因顾C中除去W?{w}和X?{x}后～余下00的每一顾顾都恰好包含个W,X和Y的一元素～而个W,X和Y各有q元素且个互不相交～所以C'中任何q顾顾的顾顾一定顾顾个于q三元顾～顾个q三元顾成个构M的一匹配。个反之～顾M的任意一匹配～可以用个C中顾顾的q顾顾顾顾成所要个来求的含有 99 - 80J=q+2顾顾的集合。于是个M包含一匹配且顾个当当C中存在所顾子科技大顾算机院顾小学学丰12,6,18 要求的顾顾子顾。? 顾算的顾顾性第8章　NP完全性顾明最后一顾顾明顾型～大概也是最顾顾的一顾顾明顾型～是分量顾顾。在8.1顾中顾出的顾于三顾匹配～顾点覆盖和哈密顾回路的NP完全性顾明都是顾顾顾型的顾明的典型例子。 99 - 81 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明的基本它思想是用目顾顾顾的顾例顾顾某些“分量”～能顾把顾些分量顾合在一起“顾顾”已知的NP完全顾顾的顾例。在顾三例子中个有顾基本顾型的分量～一顾可以看作“两顾顾”;例如～顾顾顾点～顾顾顾量的顾顾顾,～一顾用“真另来顾顾性顾”;例如～顾顾是否覆盖每一条顾～顾顾是否顾足每一子句,。顾些分量在个目顾顾例中以下述方式顾接在一起～把顾顾分量顾在顾顾性顾分量上～而顾顾性顾分量顾顾所作的顾顾是否顾足要求的顾束。分量之顾的相互作用顾既个生在整直接的顾接顾;例如在从3SAT到VC的顾顾中把顾真安排分量顾接在顾足性顾顾分量上的顾,～也顾生在整顾顾个体从束中;例如在顾3SAT到VC的顾顾中的顾界限K～同所有分量的顾顾顾一它随构个真起保顾每一顾安排分量恰好包含覆盖中的一顾点～且每一顾足性顾顾分量个并个恰好包含覆盖中的顾点,。两个 99 - 82 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明　更一般地～只要在顾明中能顾把构来造出的顾例看作一顾分量～根据顾定的顾例每一顾分量完成某顾功能～那顾顾顾顾明就可以看成是一分量顾顾顾明。在第个7章用顾明来Cook定理的一般性顾顾就是一好的例子。个很个那六子句顾中的每一子句顾是一顾顾型的分量。个　因顾分量顾顾法顾明多半是相顾的～而且我顾已顾顾出当了若干个个个例子～所以顾一顾顾顾再顾出一例子。顾例子与很它通常的例子不一顾～顾明了一顾方法～顾顾方法顾于把顾顾顾到其顾顾有用。顾几个它很个个与区目顾顾顾是一顾排序顾顾有顾的顾度顾顾～在8.2.2顾中已顾顾明顾排序顾顾是区NP完全的。 99 - 83 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明顾例,“任顾”集T～每一个t?T的“顾度”顾1～“截止 + 顾顾”顾d(t)?Z～此外顾有T上的偏序,’以及非顾整数K?|T|。顾,是否存在一“顾个度表”σ,T?{0,1,...,|T|-1} 使得,当t?t顾～σ(t)?σ(t’)～99 - 84 顾子科技大顾算机院顾小学学丰12,6,18 当t,t’顾σ(t),σ(t’), 且并|{t?T|σ(t)+1,d(t)}|?K, 顾算的顾顾性第8章　NP完全性顾明顾明,顾顾G=(V,E)和正整数J?|V|顾成顾的任意一顾例。个最少拖延排序顾顾的顾顾顾例包含任顾集T,{V,E}～K,|E|-(J(J-1)/2)以及如下定顾的偏序和截止顾顾, t?t’ ? t?V～t'?E且顾点并t是顾t'的一个端点1 J(J1)/2,如果tE+?: d(t)=, |V||E|,如果tV+?: 于是顾顾于每一顾点的“分量”是一顾个截止顾顾顾|V|+|E|的任顾～而顾顾于每一顾的“分量”是一顾条截止顾顾顾J(J+1)/2的任顾。在所要求的顾度中根据偏序顾系～顾顾于一顾的任顾条必顾出顾 99 - 85 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明在顾顾于的它两个端点的任顾之后～而且只有顾顾于顾的任顾才有拖延;在的它截止顾顾之后完成,的危顾。用顾示意所要求的顾度表要方便些～如顾8-9所示。我顾可以顾顾～在顾顾于顾的任顾的截止顾顾之前的顾度表部分是“顾顾顾分量与个”。在顾截止顾顾之前能安排J(J+1)/2顾任顾。顾了不超顾顾定的拖延任顾的数目～至少有J(J-1)/2顾顾顾“提前完成的”任顾是顾顾于顾的任顾。但是～如果一顾顾顾于顾的任顾在的它截止顾顾之前～那顾顾顾于的它个端点的顾点任顾也一定在顾截止顾顾之前。在J(J-1)/2不同的顾中至少包含条J顾点;且顾顾些顾形成顾个当当J顾个点上的完全顾顾才是顾顾,。因此～在“提前完成的”任顾中至少有J顾顾顾于顾点的任顾。但是～在顾顾于顾的 99 - 86 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明顾的顾点顾的顾 J顾顾顾于 J(J-1)/2顾顾顾 |V|-J顾顾顾 |E|-J(J-1)/2顾顾点的任顾于顾的任顾于顾点的任顾顾顾于顾的任顾 J(J1)+ 0 |V|+|E| 2 顾顾顾8-9 我顾所要求的顾于最少拖延排序顾例的顾度表的顾解～顾顾例顾顾于大小顾个J的顾的顾例 99 - 87 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明任顾的截止顾顾之前至多有安排 J(J+l)/2-J(J-1)/2=J 顾顾顾于顾点的任顾的余地。因此～任何一顾顾的顾个度表在顾个截止顾顾之前都必顾恰好有J顾顾顾于顾点的任顾和J(J-1)/2顾顾顾于顾的任顾～而顾些顾顾于顾点的任顾和顾顾于顾的任顾一定顾顾于G中的一含有个J顾点的顾。相个反地～如果G包含一大小顾个J的完全子顾～那顾可以像顾8-9中那顾构造出要求的顾度表。? 99 - 88 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明在上顾中～我顾两个介顾了如何顾明某新顾顾的NP完全性～顾明是即它NP顾中最顾的顾顾。那顾～我顾自然顾会～顾顾明某顾顾顾怎个NP顾中最容易的顾顾～顾明是即它P顾顾顾,呢由定顾～要顾明一顾顾个Π于属P～就要顾明存在一个求解它的多顾式顾顾DTM程序～而由定型顾机确灵 DTM顾顾中任一合理顾算机的行方式之顾的多顾式顾与运顾等价性～顾等于要求我顾顾明存在一顾算顾顾顾顾性顾多顾个式的通常意顾下的算法～可用它来求解顾顾Π。 99 - 89 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明先顾顾出求解顾顾Π的一算法个～然后顾明其正性确～可利用顾算即法精确求解顾顾Π～最后～通顾仔顾分析算法的顾顾顾程顾顾所需来估它的顾的顾算工作量～其即顾算顾顾性～若所得顾顾可用顾顾顾模;估参数如顾入顾度、顾顾顾数个数来等,的一多顾式函界定～顾表明顾算法顾多顾式顾顾算法～而得到顾顾从P属于Π。如背包顾顾、排序顾顾等等。采用顾顾方法顾明顾顾于来属P顾～一般顾要充分利用所顾明顾顾的具体特性～以便顾顾出适的当求解算法,使得能顾成它构求解原顾顾的多顾式顾顾算法。顾而～顾同一顾顾,顾可能存在多顾不同的顾明方法～如排序顾顾有顾顾排序、入插排序和冒泡排序等算法。因此～顾顾顾方法～由于其顾于具体与很个顾顾的依顾性多顾性～顾指定一通用的顾明步顾或方法。 99 - 90 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明代替顾顾出具体另属的求解算法～一顾顾明顾顾于P的方法是通顾某顾顾顾或顾顾推理顾行来。常顾的技巧有,顾明可采用一些顾顾的、可在多顾式顾顾完成的顾顾方法～内将原顾顾顾顾顾一已知的另P顾顾顾的求解～顾明可通顾顾推、分解等方法顾原顾顾顾行顾来很化～使顾化后的顾顾容易在多顾式顾顾内求解～而所采用的分解等策略也可在多顾式顾顾内完成～直接考察原顾顾的可行解所可能存在的各顾情形～然顾些可能的不同情形不超顾顾顾顾模的某多顾式当会个～顾明在每顾情下并况内均可在多顾式顾顾求解原顾顾。 99 - 91 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明顾例,有顾的顾量集合U上的子句顾C={c,c,...,c}～12m 其中|c|=2～1?i?m。i 顾,顾于U是否存在顾足C中所有子句的顾顾顾,真 99 - 92 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明若二元合取范式(合即个两个取范式中每子句均含有顾量)H不含顾量u～且u,，u不等于y,y,…,y,z,z,…,z～顾二元合取范式iii12k12h G,H?(u?y)?(u?y)?…?(u?y)i1i2ik ?(，u?z)?(，u?z)?…?(，u?z)i1i2ih是否是可顾足的与 G'H((yz))ij 1ik是否是可顾足的是等价的。1jh 99 - 93 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明顾明　令 m G(xy)= ii =i1 其中x,y?{u,，u,u,，u,…,u,，u,}～而U,ii1122nn {u,u,12 …,u}～考顾以下顾情,几况n 1)　x?y,u?，u或，u?u～因顾顾顾的二iijjjj 元子句顾是取顾顾～所以可真自顾消去～就是顾可以顾顾G中 99 - 94 顾子科技大顾算机院顾小学学丰不存在顾顾的子句～12,6,18 顾算的顾顾性第8章　NP完全性顾明 2)　顾于顾量两个u和u～在G中出顾(u?u)?(u?ijiji，uj)顾～若取u顾“F”～顾G顾“F”～若取uii顾“T”～顾G有三顾可能的顾果,一是G顾“T”～即它可顾足～二是G顾“F”～不可顾足即它～三是可以消去若干个子句～于是得到顾化了的新的合取范式～此顾顾顾顾顾于新的二元可顾足性顾顾。如上～在顾化了的新的G中～子句至多顾个数n(n-1)～且上述的顾个化顾程可在n的多顾式顾顾完成。在顾内化了的G中～顾任意的顾量～其否定必含于其子句中。它因此～G中出顾的所有顾量都顾足引理8-2中顾于u的条i件～有即2)的推广形式 99 - 95 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明3) G,H?(u?y)?…?(u?y)i1ik ?(，u?z)?…?(，u?z)～i1ih 从而由引理8-2知G的可顾足性以下合与取范式的可顾足性相互等价 G'H((yz))= ij 1ik 1jh 但顾于G’～顾量的个数减个却少了一～成顾n-1。个G有m子句～个个消去一顾量～化顾G’～而G’的子句 22个数顾m+kh-k-h?n(n-1)+n(n-1)。顾顾的化顾手顾可在n的多顾式顾顾完成。顾顾有内n-1顾量～个m+kh-k-h个子句。若顾其中u顾顾顾“T”～顾，u顾顾顾“F”～顾可ii 在n的多顾式顾顾内判定G的可顾足性。 99 - 96 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明顾于G’～可再顾顾1),2)或3)的化顾～子句个数减又少到(n-1)(n-2)。再利用引理8-2～又可消去一顾个量。象顾顾～顾量一地少下去～要顾在个数个个减化顾顾程中～在1)或2)中能判定顾顾是否可顾足～要顾到最后化顾一顾量～于是个也可判定。顾顾～至多重顾顾行1),2)或3)n-1次～便可得到二元可顾足性顾顾顾顾判定顾顾的解答～且顾的顾顾顾顾性于囿n的多顾式～故2SAT?P。 99 - 97 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明在8.1.3中～我顾指出～一般顾上的独立集顾顾是属于NPC顾顾顾的～但限于当独偶顾顾～相顾的立集顾顾顾要容易求解得多～因顾是于它属P顾顾顾的。偶顾的独立集的判定顾顾可描述如下, 顾例,偶顾G=(V,E,V)和正整数J?|V?V|。1212 顾,G是否包含一个独立集V';即V' V使得顾任意u,v ?V'～顾(u,v)都不在E中,～使得|V'|?J, 99 - 98 顾子科技大顾算机院顾小学学丰12,6,18 顾算的顾顾性第8章　NP完全性顾明顾明,由偶顾的定顾～V中的任意两个顾点互不相顾～V2中1 的任意两个独个数顾点互不相顾～所以最大立集中所含顾点顾, Max{|V|+|V-V|～|V|+|V-V|} 12212112 其中V是V中与V的某顾点相顾的顾点集～个V是V中与2121121V的某顾点相顾的顾点集。个2 在求出最大独个数与立集的顾点后～J顾行比顾可直接得即到判定顾顾的解答。而顾求出最大独个数坏立集的顾点之顾～在最情下需顾况 Max{|V|+|V|×|V|～|V|+|V|×|V|} 112212 次顾顾～顾顾算量顾然不超顾顾顾顾模的一多顾式～个个独故偶顾的立集顾顾必是P顾顾顾。 99 - 99 顾子科技大顾算机院顾小学学丰12,6,18

                    本文档为【计算的复杂性 第八章 NP完全性证明!10】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

计算的复杂性 第八章 NP完全性证明!10

你可能还喜欢

计算的复杂性第八章 NP完全性证明!10