计算的复杂性 第八章 NP完全性证明.ppt

Email :******@uestc. 2017 年2月23日星期四顾顾小小丰丰 99 - 2 第8章 NP 完全性证明电子科技大学计算机学院顾小丰计算的复杂性 2017-2-23 ?P类问题的证明第8章 NP完全性证明?六个基本的 NP完全问题?NP完全性的证明方法?三元可满足性?三维匹配?节点覆盖和团?哈密顿回路?划分?限制法?局部替换法?分量设计法 99 - 3 第8章 NP 完全性证明电子科技大学计算机学院顾小丰计算的复杂性 2017-2-23 六个基本的 NP完全问题 当经验丰富的研究人员面对一个要证明 NP 完全性的问题Π时, 他们的有利条件是有经验可以利用。他们可能在过去已经证明过类似的问题Π'的NP 完全性,或者见过这样一个证明。这可能使他们试图模仿Π'的NP 完全性证明来证明Π的NP 完全性,或者把Π' 本身变换到Π来证明Π的NP 完全性。在很多情况下,这样可能很容易地得到了Π的NP完全性证明。 可是,常常找不到已知的类似于Π的NP 完全问题。在这种情况下,研究人员可能不能凭直觉从这数百个已知的 NP 完全问题中挑选出一个最合适的问题作这个证明的基础。然而,经验仍然能够把选择的范围缩小到一个基本问题的核心,这些问题在过去曾经是很有用的。虽然在理论上任何已知的 NP 完全问题都能够用来证明新问题的NP 完全性,但是在实际上某些问题似乎更适合用于证明。下述六个问题就是这种最常使用的问题,因而我们认为这六个问题能够作为初学者的已知的 NP完全问题的“基本核心”。 99 - 4 第8章 NP 完全性证明电子科技大学计算机学院顾小丰计算的复杂性 2017-2-23 1. 三元可满足性( 3sat ) 实例: 有穷的变量集合 U上的子句类 C={c 1,c 2,...,c m},其中|c i|=3 ,1≤i≤m。 问: 对于 U是否存在满足 C中所有子句的真值赋值? 2. 三维匹配( 3DM ) 实例:集合 M?W×X×Y,这里 W,X 和Y是三个不相交的集合, 且有相同的元素个数 q。 问: M是否包含一个匹配,即是否有子集 M’?M使得|M| ’=q且M'中任何两个元素的任何坐标都不相同? 99 - 5 第8章 NP 完全性证明电子科技大学计算机学院顾小丰计算的复杂性 2017-2-23 3. 节点覆盖( VC) 实例: 图G=(V,E) 和正整数 k≤|v| 。 问: G是否有大小不超过 k的节点覆盖,即是否有子集 V’? V使得|V’|≤k并且对每一条边(u,v) ∈E,u 和v中至少有一个属于 V'? 4. 团实例:图 G=(V,E) 和正整数 J≤|V| 。 问: G是否包含大小不小于 J的团,即是否有子集 V’?V, 使得|V’|≥J并且 V’中每两个节点都由 E中的一条边连接着。 99 - 6 第8章 NP 完全性证明电子科技大学计算机学院顾小丰计算的复杂性 2017-2-23 5. 哈密顿回路( HC) 实例:图 G=(V,E) 。 问: G是否包含一条哈密顿回路,即是否有 G的节点排列次序<v 1,v 2,...,v n>使得(v n,v 1)∈E和(v I,v i+1)∈E, 1≤i<n?这里 n=|V| 。 6. 划分实例: 有穷集合 A以及每一个 a∈A的“大小”S(a) ∈Z +。问: 是否有子集 A'?A使得??????'AAa'Aa)a(S)a(s? 99 - 7 第8章 NP 完全性证明电子科技大学计算机学院顾小丰计算的复杂性 2017-2-23 证明顺序我们将从证明这六个问题是 NP 完全的开始,阐述证明 NP 完全性的方法,并且在合适的时候指出这些问题的变种,它们的 NP完全性或多或少可以直接地从这些基本问题的 NP完全性得到。第一个变换将从可满足性开始,因为到现在为止我们只知道这么一个“已知的”NP 完全问题。然而在进行这六个证明的过程中,我们已知的 NP 完全问题会不断地增加,并且在证明问题Π的 NP 完全性时可以利用所有在Π之前证明了 NP 完全性的问题。图 8-1 说明我们把哪个问题变换到这六个基本问题中的每一个。如果把一个问题变换到另一个问题,这里就画一个箭头从第一个问题指向第二个问题。即使当他的顺序和我们的一样精炼时,为了说明某些一般性的证明方法,我们有时还是修改或替换了原来的变换。 99 - 8 第8章 NP 完全性证明电子科技大学计算机学院顾小丰计算的复杂性 2017-2-23 图8-1 在证明六个基本问题的 NP完全性中使用的变换的顺序图可满足性 3SAT 划分 HC 团 3DM VC99 - 9 第8章 NP 完全性证明电子科技大学计算机学院顾小丰计算的复杂性 2017-2-23 三元可满足性 三