第十章 NP完全问题

算法设计与分析

AlgorithmsDesignandAnalysis

赵廷刚兰州城市学院数学学院2013.3本章内容10.1引言10.2P类10.3NP类10.4NP完全问题10.5co-NP类10.6NPI类10.7四种类之间的关系10.1引言有这样一类问题：至今没有找到有效算法，而且将来也不大可能发现它们的有效算法。设Π是任意问题，如果对问题Π存在一个算法，它的时间复杂性是O(nk),其中n是输入大小，k是非负整数，我们说存在着求解问题Π的多项式时间算法。现实世界中的许多有趣问题并不属于这个范畴，即求解这些问题所需要的时间量是要用指数或超指数函数(2n或n!)来测度。计算机科学界的共识：存在多项式时间算法的问题是易于求解的，而那些不大可能存在多项式时间算法的问题是难解的。NP完全问题是难解问题的一个子类。它包含许许多多问题，其中还有数百个著名的问题，它们有一个共同特性，即如果它们中的一个是多项式可解的，那么所有其它的问题也是多项式可解的。非常有趣的是，它们中的许多是普通的现实问题，就是说它们来源于现实世界的实际应用问题。此外，现存的求解这些问题的算法的运行时间，对于中等大小的输入也需要几百或几千年。判定问题：问题使它的解只有两个结论：是或否。最优化问题：问题关心某个量的最大化或最小化。例10.1

设S是一个实数序列，ELEMENTUNIQUENESS问题为，是否S中的所有数都是不同的.判断问题：ELEMENTUNIQUENESS

输入：一个整数序列S.问题：在S中存在两个相等的元素吗？最优问题：ELEMENTCOUNT

输入：一个整数序列S.输出：一个在S中频度最高的元素。这个问题在最优时间O(nlogn)

解决，它是易解的。例10.2

给出一个无向图G=(V,E)，用k种颜色对G着色是这样的问题：对于V中的每一个顶点用k种颜色中的一种对它着色，使图中没有两个相邻顶点有相同的颜色.判断问题：COLORING

输入：一个无向图G=(V,E)和一个正整数k≥1.问题：G可以k着色吗？即G最多可以用k种颜色着色吗？最优问题：CHROMATICNUMBER

输入：一个无向图G=(V.E).输出：G的色数。这个问题是难解的。如果k=3，就是3着色问题。对一个图着色，使图中没有两个相邻的顶点有相同的颜色，所需的最少颜色数，称为G的色数，记为χ(G).例10.3

给出一个无向图G=(V,E)，对于某个正整数k，G中大小为k的团集是指G中有k个顶点的一个完全子图。判断问题：CLIQUE

输入：一个无向图G=(V,E)和一个正整数k.问题：G有大小为k的团集吗？最优问题：MAX-CLIQUE

输入：一个无向图G=(V,E).输出：一个正整数k，它是G中最大团集的大小。10.2P类定义10.1

设A是求解问题∏的一个算法，如果在展示问题∏的一个实例时，在整个执行过程中每一步都只有一种选择，则称A是确定性算法。因此如果对于同样的输入，实例一遍又一遍地执行，它的输出从不改变。定义10.2

判断问题的P类由这样的问题组成，它们的yes/no解可以用确定性算法在运行多项式步数内得到，例如在O(nk)步内得到，其中k是某个非负整数，n是输入大小。

不是每一个判定问题都能够在多项式的时间内求解。

某些判断问题是不能用任何算法求解的。这些问题称为不可判定问题。排序问题：给出一个n个整数的表，它们是否按非降序排列？不相交集问题：给出两个整数集合，它们的交集是否为空？最短路问题：给出一个边上有正权的有向图G=(V,E),两个特异的顶点s,t∈V和一个正整数k，在s和t之间是否存在一条路径，它的长度最多是k。2着色问题：给出一个无向图G,它是否可2着色？2可满足问题：给出一个合取范式(CNF)形式的布尔表达式f，这里每个子句恰好由两个文字组成。问f是可满足的吗？下列问题属于P类：如果对任意问题类C，问题∏的补也在C中，我们说问题类∏∈C在补运算下是封闭的。例如，2着色问题的补可以陈述如下：给出一个图G，它是不2可着色的吗？我们称这个问题是NOT-2-COLOR问题。

可以证明，NOT-2-COLOR问题是属于P类的。即2着色问题在补运算下是封闭的。定理10.1

P类问题在补运算下是封闭的。10.3NP类不确定性算法

设对于输入x，一个不确定算法由两步组成：(a)猜测阶段（非确定）。在这个阶段产生一个任意字符串y，它可能对应于输入实例的一个解，也可以不对应解。事实上，它甚至可能不是所求解的合适形式，它可能在不确定性算法的不同次运行中不同。它仅仅要求在多项式步数内产生这个串，即在O(ni)时间内，这里n=|x|，i是非负整数。对许多问题，这一阶段可以在线性时间内完成。(b)验证阶段（确定）。验证两件事。首先，检验y是否有合适的形式，如果不是，则算法停下来并回答no；另一方面，如果y有合适形式，那么算法继续检查它是否是问题实例x的解，如果它确实是实例x的解，那么它停下并且回答yes，否则它停下并回答no。我们要求这个阶段在多项式步数内完成，即在时间O(nj)内完成,这里j是一个非负整数。定义10.3

判断问题的NP类由这样的问题组成:对于它们存在着多项式时间内运行的不确定性算法。设A是问题∏的一个不确定行算法，我们说A接受问题∏的实例I,当且仅当对于输入I存在一个导致yes回答的猜测。换句话说，A接受I当且仅当可能在算法的某次执行上它的验证阶段将回答yes。要强调的是，如果算法回答no，那么着并不意味着A不接受它的输入，因为算法可能猜测了一个不正确的解。

至于一个不确定性算法的运行时间，它仅仅是两个运行时间的和：猜测阶段和验证阶段的时间。P类和NP类之间，有下面不同点：

P是一个判断问题类，这些问题可以用一个确定性算法在多项式时间内判定或解出；NP是一个判断问题类，这些问题可以用一个确定性算法在多项式时间内检验或验证它的解。10.4NP完全问题

术语“NP完全”表示NP中判定问题的一个子类，它们在下述意义下是最难的，即如果它们中的一个被证明用多项式时间确定性算法可解，那么NP中的所有问题用多项式时间确定算法可解，即P=NP。定义10.4

设Π和Π’是两个判断问题。如果存在一个确定性算法A，它的行为如下，当给A展示问题Π的一个实例I,算法A可以把它变换为问题Π’的实例I’,使得当且仅当对I’回答yes时，对I回答yes,而且，这个变换必须在多项式时间内完成。那么我们说Π多项式时间归约到Π’,用符号Π∝polyΠ’表示。定义10.6

一个判断问题Π称为是NP完全的，如果下列两个条件同时成立：

(a)Π在NP中;

(b)对于NP中的每一个问题

Π’,Π’

∝polyΠ。定义10.5

一个判断问题Π称为是NP困难的，如果对NP中每一个问题Π’,

Π’

∝polyΠ表示。

这样，在NP完全问题∏和NP困难问题∏’间的差别是：∏必须是NP类的而∏’可能不在NP中。10.4.1可满足性问题合取范式(CNF)：给出一个布尔公式f,如果他是子句的合取，就称它为合取范式(CNF).

例如：可满足的(CNF)：一个公式如果对它的变元存在一个真值的指派是他为真，则称为可满足的。

因此，为了证明一个问题∏是NP完全问题，仅需证明下面两条：(1)∏∈NP；(2)存在一个NP完全问题∏’,使∏’∝poly∏.10.4.2顶点覆盖、独立集和团集问题团集：给出一个无向图G=(V,E)和一个正整数k,G包含一个大小为k的团集吗？(一个G中大小为k的团集是G中k个顶点的一个完全子图）。顶点覆盖：给出一个无向图G=(V,E)和一个正整数k,是否存在大小为k的子集C包含于V,使E中的每条边至少和C中的一个顶点关联？独立集：给出一个无向图G=(V,E)和一个正整数k,是否存在k个顶点的子集S包含于V，使得对于每一对顶点u,w∈S,(u,w)∉E？可以证明以上三个问题都是