第8章NP完全性理论案例.ppt

第8章 NP完全性理论 8.1 计算模型 8.1.1 随机存取机RAM 8.1.2 随机存取存储程序机RASP 8.1.3 RAM模型的变形与简化 8.1.4 图灵机 8.1.5 图灵机模型与RAM模型的关系 8.1.6 问题变换与计算复杂性归约 8.1.1 随机存取机RAM 1. RAM的结构 8.1.1 随机存取机RAM 2. RAM程序 8.1.1 随机存取机RAM 3. RAM程序的耗费标准 8.1.2 随机存取存储程序机RASP 1. RASP的结构 RASP的整体结构类似于RAM，所不同的是RASP的程序是存储在寄存器中的。每条RASP指令占据2个连续的寄存器。第一个寄存器存放操作码的编码，第二个寄存器存放地址。RASP指令用整数进行编码。 2. RASP程序的复杂性 不管是在均匀耗费标准下，还是在对数耗费标准下，RAM程序和RASP程序的复杂性只差一个常数因子。在一个计算模型下T(n)时间内完成的输入-输出映射可在另一个计算模型下模拟，并在kT(n)时间内完成。其中k是一个常数因子。空间复杂性的情况也是类似的。 8.1.3 RAM模型的变形与简化 1. 实随机存取机 RRAM 8.1.3 RAM模型的变形与简化 2. 直线式程序 8.1.3 RAM模型的变形与简化 3. 位式计算 8.1.3 RAM模型的变形与简化 4. 位向量运算(Bit Vector Operations) 8.1.3 RAM模型的变形与简化 5. 判定树 8.1.3 RAM模型的变形与简化 6. 代数计算树ACT 8.1.3 RAM模型的变形与简化 7. 代数判定树ADT(Algebraic Decision Tree) 8.1.4 图灵机 1. 多带图灵机 8.1.4 图灵机 8.1.4 图灵机 8.1.5 图灵机模型与RAM模型的关系 8.1.6 问题变换与计算复杂性归约 8.1.6 问题变换与计算复杂性归约 8.1.6 问题变换与计算复杂性归约 8.2 P类与NP类问题 8.2.1 非确定性图灵机 8.2.2 P类与NP类语言 8.2.3 多项式时间验证 8.2.1 非确定性图灵机 8.2.2 P类与NP类语言 8.2.2 P类与NP类语言 8.2.2 P类与NP类语言 8.2.3 多项式时间验证 8.3 NP完全问题 8.3.1 多项式时间变换 8.3.2 Cook定理 8.3.1 多项式时间变换 8.3.1 多项式时间变换 8.3.2 Cook定理 8.4 一些典型的NP完全问题 8.4.1 合取范式的可满足性问题（CNF-SAT） 8.4.2 3元合取范式的可满足性问题（3-SAT） 8.4.3 团问题CLIQUE 8.4.4 顶点覆盖问题 （VERTEX-COVER） 8.4.5 子集和问题 （SUBSET-SUM） 8.4.6 哈密顿回路问题 （HAM-CYCLE） 8.4.7 旅行售货员问题TSP 要证明CNF-SAT∈NPC，只要证明在Cook定理中定义的布尔表达式A，…，G或者已是合取范式，或者有的虽然不是合取范式，但可以用布尔代数中的变换方法将它们化成合取范式，而且合取范式的长度与原表达式的长度只差一个常数因子。 问题描述：给定一个合取范式α，判定它是否可满足。 如果一个布尔表达式是一些因子和之积，则称之为合取范式，简称CNF(Conjunctive Normal Form)。这里的因子是变量 或 。例如： 就是一个合取范式，而 就不是合取范式。 证明思路： 3-SAT∈NP是显而易见的。为了证明3-SAT∈NPC，只要证明CNF-SAT∝p 3-SAT，即合取范式的可满足性问题可在多项式时间内变换为3-SAT。 问题描述：给定一个3元合取范式α，判定它是否可满足。 证明思路： 已经知道CLIQUE∈NP。通过3-SAT∝pCLIQUE来证明CLIQUE是NP难的，从而证明团问题是NP完全的。 问题描述：给定一个无向图G=(V，E)和一个正整数k，判定图G是否包含一个k团，即是否存在，V’?V，|V’|=k，且对任意u，w∈V’有(u，w)∈E。 证明思路： 首先，VERTEX-COVER∈NP。因为对于给定的图G和正整数k以及一个“证书”V’，验证|V’|=k，然后对每条边(u，v)∈E，检查是否有u∈V’或v∈V’，显然可在多项式时间内完成。 其次，通过CLIQUE∝pVERTEX-COVER来证明顶点覆盖问题是