算法设计与分析（王佳）08NP完全性理论.pptVIP

10.3.2 Cook定理 定理8-7(Cook定理)：布尔表达式的可满足性问题SAT是NP完全的。 证明：SAT的一个实例是k个布尔变量 ，…， 的m个布尔表达式 ，…， 若存在各布尔变量 (1≤i≤k)的0，1赋值，使每个布尔表达式 (1≤i≤m)都取值1，则称布尔表达式 … 是可满足的。 SAT∈NP是很明显的。对于任给的布尔变量 ，…， 的0，1赋值，容易在多项式时间内验证相应的 … 的取值是 否为1。因此，SAT∈NP。 现在只要证明对任意的L∈NP有L∝pSAT即可。 （详细证明见书本P307～310） 10.4 一些典型的NP完全问题 部分NP完全问题树 10.4.1 合取范式的可满足性问题（CNF-SAT） 要证明CNF-SAT∈NPC，只要证明在Cook定理中定义的布尔表达式A，…，G或者已是合取范式，或者有的虽然不是合取范式，但可以用布尔代数中的变换方法将它们化成合取范式，而且合取范式的长度与原表达式的长度只差一个常数因子。 问题描述：给定一个合取范式α，判定它是否可满足。 如果一个布尔表达式是一些因子和之积，则称之为合取范式，简称CNF(Conjunctive Normal Form)。这里的因子是变量 或 。例如： 就是一个合取范式，而 就不是合取范式。 10.4.2 3元合取范式的可满足性问题（3-SAT） 证明思路： 3-SAT∈NP是显而易见的。为了证明3-SAT∈NPC，只要证明CNF-SAT∝p 3-SAT，即合取范式的可满足性问题可在多项式时间内变换为3-SAT。 问题描述：给定一个3元合取范式α，判定它是否可满足。 10.4.3 团问题CLIQUE 证明思路： 已经知道CLIQUE∈NP。通过3-SAT∝pCLIQUE来证明CLIQUE是NP难的，从而证明团问题是NP完全的。 问题描述：给定一个无向图G=(V，E)和一个正整数k，判定图G是否包含一个k团，即是否存在，V’?V，|V’|=k，且对任意u，w∈V’有(u，w)∈E。 10.4.4 顶点覆盖问题 （VERTEX-COVER） 证明思路： 首先，VERTEX-COVER∈NP。因为对于给定的图G和正整数k以及一个“证书”V’，验证|V’|=k，然后对每条边(u，v)∈E，检查是否有u∈V’或v∈V’，显然可在多项式时间内完成。 其次，通过CLIQUE∝pVERTEX-COVER来证明顶点覆盖问题是NP难的。 问题描述：给定一个无向图G=(V，E)和一个正整数k，判定是否存在V’?V，|V’|=k，使得对于任意(u，v)∈E有u∈V’或v∈V’。如果存在这样的V’，就称V’为图G的一个大小为k顶点覆盖。 10.4.5 子集和问题 （SUBSET-SUM） 问题描述：给定整数集合S和一个整数t，判定是否存在S的一个子集S’?S，使得S’中整数的和为t。例如，若S={1，4，16，64，256，1040，1041，1093，1284，1344}且t=3754，则子集S’={1，16，64，256，1040，1093，1284}是一个解。 证明思路： 首先，对于子集和问题的一个实例S，t，给定一个“证书”S’，要验证t= 是否成立，显然可在多项式时间内完成。因此，SUBSET-SUM∈NP； 其次，证明VERTEX-COVER∝pSUBSET-SUM。 10.4.6 哈密顿回路问题 （HAM-CYCLE） 证明思路： 首先，已知哈密顿回路问题是一个NP类问题。 其次，通过证明3-SAT∝pHAM-CYCLE， 得出：HAM-CYCLE∈NPC。 问题描述：给定无向图G=(V，E)，判定其是否含有一哈密顿回路。 10.4.7 旅行售货员问题TSP 首先，给定TSP的一个实例(G，c，k)，和一个由n个顶点组成的顶点序列。验证算法要验证这n个顶点组成的序列是图G的一条回路，且经过每个顶点一次。另外，将每条边的费用加起来，并验证所得的和不超过k。这个过程显然可在多项式时间内完成，即TSP∈NP。 其次，旅行售货员问题与哈密顿回路问题有着密切的联系。哈密顿回路问题可在多项式时间内变换为旅行售货员问题。即HAM-CYCLE∝pTSP。从而，旅行售货员问题是NP难的。 因此，TSP∈NPC。 问题描述：给定一个无向完全图G=(V，E)及定义在V?V上的一个费