第8章NP完全性理论试卷.ppt

8.4 一些典型的NP完全问题 部分NP完全问题树 8.4.1 合取范式的可满足性问题（CNF-SAT） 要证明CNF-SAT∈NPC，只要证明在Cook定理中定义的布尔表达式A，…，G或者已是合取范式，或者有的虽然不是合取范式，但可以用布尔代数中的变换方法将它们化成合取范式，而且合取范式的长度与原表达式的长度只差一个常数因子。 问题描述：给定一个合取范式α，判定它是否可满足。 如果一个布尔表达式是一些因子和之积，则称之为合取范式，简称CNF(Conjunctive Normal Form)。这里的因子是变量 或 。例如： 就是一个合取范式，而 就不是合取范式。 8.4.2 3元合取范式的可满足性问题（3-SAT） 证明思路： 3-SAT∈NP是显而易见的。为了证明3-SAT∈NPC，只要证明CNF-SAT∝p 3-SAT，即合取范式的可满足性问题可在多项式时间内变换为3-SAT。 问题描述：给定一个3元合取范式α，判定它是否可满足。 8.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。 8.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顶点覆盖。 8.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。 8.4.6 哈密顿回路问题 （HAM-CYCLE） 证明思路： 首先，已知哈密顿回路问题是一个NP类问题。 其次，通过证明3-SAT∝pHAM-CYCLE， 得出：HAM-CYCLE∈NPC。 问题描述：给定无向图G=(V，E)，判定其是否含有一哈密顿回路。 8.4.7 旅行售货员问题TSP 首先，给定TSP的一个实例(G，c，k)，和一个由n个顶点组成的顶点序列。验证算法要验证这n个顶点组成的序列是图G的一条回路，且经过每个顶点一次。另外，将每条边的费用加起来，并验证所得的和不超过k。这个过程显然可在多项式时间内完成，即TSP∈NP。 其次，旅行售货员问题与哈密顿回路问题有着密切的联系。哈密顿回路问题可在多项式时间内变换为旅行售货员问题。即HAM-CYCLE∝pTSP。从而，旅行售货员问题是NP难的。 因此，TSP∈NPC。 问题描述：给定一个无向完全图G=(V，E)及定义在V?V上的一个费用函数c和一个整数k，判定G是否存在经过V中各顶点恰好一次的回路，使得该回路的费用不超过k。 人有了知识，就会具备各种分析能力， 明辨是非的能力。 所以我们要勤恳读书，广泛阅读， 古人说“书中自有黄金屋。 ”通过阅读科技书籍，我们能丰富知识， 培养逻辑思维能力； 通过阅读文学作品，我们能提高文学鉴赏水平， 培养文学情趣； 通过阅读报刊，我们能增长见识，扩大自己的知识面。 有许多书籍还能培养我们的道德情操， 给我们巨大的精神力量， 鼓舞我们前进。 * 欢迎辞 * 第5章 回溯法 四川理工学院 杨维剑 算法分析与设计教案 杨维剑 第5章 回溯法 四川理工学院 杨维剑 算法分析与