《算法设计与分析NP完全问题》由会员分享，可在线阅读，更多相关《算法设计与分析NP完全问题（3页珍藏版）》请在金锄头文库上搜索。
1、NP 完全问题研究 P=NP 的问题有两条基本思路：1证明 NP 类中的某些问题是难解的，从而得到 NPP。但是要证明这一点几乎同证明 P=NP 一样困难。2考察 NP 类中问题之间的关系，从中找到一些具有特殊性质的、与 P 类问题显著不同的问题。沿着这一路线人们已经证明了在 NP 类中存在被称为 NP 完全的子类，简称 NPC 问题，并由此发展了一套著名的 NP 完全理论。本节简要先介绍 NP 完全性理论。为此，首先给出各语言之间的多项式变换的概念。定义 1 所谓从一个语言 到另一个语言 的多项式变换是指*1L*2L满足下面两个条件的函数 ，2*1:f(1) 存在计算 的一个多项式时间 DT
2、M 程序；f(2) 对于所有的 有： 当且仅当 。*1x1L2)(Lxf用 表示存在一个从语言 到语言 的多项式变换。相应地，对于21L2判定问题 ，设 e1和 e2是相应的编码策略。若 ，则记, ,21e为 。21也可以从问题的层次来叙述：由判定问题 到判定问题 的多项式变换12是满足下列条件的函数 ，21:Df(1) 可由一个多项式时间的确定性算法来计算；f(2) 对于所有的 有： 当且仅当 。112)(Yf定义 2 称一个语言 （判定问题 ）为 NP 完全的（NPC） ，如果L，且对于所有别的语言 （判定问题 ）均有)(NPLNP NP。按照定义 2，要证明问题 是 NP 完全的，需要证
3、明所有的 NP 问题均能够经多项式变换变成 。这几乎是很难做到的。如果 NP 完全问题比较多，我们也不能对每一个这样的问题都这样验证。为此我们讨论一些 NPC 问题的有用的性质。性质 1 如果 ，则 意味着 。LPL性质 2 如果 ，则 。 LL而 且 由性质 1，2，不能推出下列结论，定理 2 设 是 NP 完全的，如果 ，则 。NPP定理 3 如果 ，则 .NP, CL定理 3 是证明 NP 完全问题的基础。但这需要一个 NPC 问题作为源问题。Cook 首先给出这样问题-可满足性问题。可满足性问题是数理逻辑中一个重要问题，它定义在布尔变量之上。给定布尔变量集 ， 上的一个真值分配是指一个
4、映射 ,21muUU。 上的一个子句 C 就是由一些布尔变量（或它们的“否” ）通过,:FTt逻辑“或”连接起来的布尔表达式。若存在对于布尔变量集 的一个真值分配，U使得该子句取值为真，则说该子句被满足。子句的集合说是可满足的，如果存在 的一个真值分配，使得集合中的每个子句的取值均为真。可满足性问题可描述如下：例 给定布尔变量之集 以及 上子句的一个集合 C。U问 是否存在 的一个真值分配，使得 C 是可满足的。Cook 定理 可满足性问题是 NP 完全问题。从 Cook 的开创性工作至今，人们已经发现并证明了数千个 NPC 问题（如，0/1 背包问题和 Hamilton 回路问题） ，总结出
5、证明 NP 完全性的几种方法，并建立了如何分析、进而近似求解 NP 完全问题的方法等一系列理论结果。以下列出几个典型的 NPC 问题： 三维匹配问题 3DM(3 Dimensional Matching)例： 给定三个互不相交的、均含有 个元素的集合 ，取qYXW,。YXWM问： 包含一个匹配吗？即是说，是否存在一个子集 ，使得M，且 中任意两个三元组都没有相同的分量。q| 三元精确覆盖问题 X3C(Exact Cover by 3-sets)例：给定有限集合 ，以及 的三元子集族 。qX3|,C问： 含有 的一个精确覆盖吗？即是说，是否存在一个子族 ，使C 得 的每个元素恰好只出现在 的一个
6、三元子集中。XC注意到，如果令 ， ，则三YWU,|,YyXxWwyx元匹配问题就转化为三元精确覆盖问题。又因为三元匹配问题是 NP 完全问题，所以，由三元匹配问题是 NPC 问题，可以知道，三元精确覆盖问题也是 NPC 问题。 顶点覆盖问题 VC（Vertex Cover）例：给定一个图 G(V,E)和一个正整数 K|V|.问：是否存在 G 的一个顶点数不超过 K 的覆盖？即是否存在一个顶点子集V/ V,|V/| K，使得对于每一条边u,vE，u 与 v 中至少有一个属于 V/. Hamilton 回路问题 HC（Hamiltonian Circuit）例：已知一个图 G(V,E)。问：G 含有一个 Hamilton 回路吗？G 的 Hamilton 回路是指包含图 G 的所有顶点的简单回路，即是 G 的顶点的一个排序：v 1,v2, , vn，其中n=|V|，使得对所有的 i: 1 i n, vi,vi+1E， v n,v1E. 划分问题例 已知一个有限集合 A 及对于每个 的一个权值 。AaZas)(问 问是否存在 A 的一个子集 ，使得 ？ Aaa 三元可满足性问题 3SAT例子 给定布尔变量的一个有限集合 U 及定义于其上的字句集,其中,21mcCmii ,21,3|问题 是否存在 U 之上的一个真赋值，使得 C 中所有的子句均被满足？
