10第十章NP完全问题解读.ppt

heyichao@sjzue.edu.cn 计算模型： 任何一种算法都应该建立在一种计算模型的基础上的； 图灵机：存储器和计算是分离的；（状态的变化处理） 图灵机计算模型：一条纸带模型，被分成多个单元，工作带头进行读写头或者左移一个单元、或者右移一个单元、或者停留在当前的单元上，其动作由它的有限状态控制器决定。 还有很多计算模型，此处略。 量子计算模型是什么样子呢？ 本章的讲解是初步入门，不讨论建立在相应计算模型上的算法讨论。 但是现实世界中许多有趣的问题并不属于这个范畴，求解这些问题所需要的时间量要用指数和超指数函数来测度。在计算机科学界已达成这样的共识，认为存在多项式时间算法的问题是易求解的，而不大可能存在多项式时间算法的问题是难解的。 非常有趣的是，它们中的许多是普通的自然问题，就是说它们来自于现实世界的实际应用问题。此外，现存的求解这些问题的算法的运行时间，对于中等大小的输入也要用几百或几千年来测度。 例10.1 设S是一个实数序列，ELEMENT UNIQUENESS问题为，是否S中的所有的数都是不同的。 这个问题是难解的，如果k被限于3，问题就是非常著名的3着色问题，甚至在图是平面的情况下也是难解的。 例如: 有一个求解图着色判定问题的算法A，则可以用二分有哪些信誉好的足球投注网站并且把算法A作为子程序来找出图G的色数。很清楚，1≤χ(G)≤n，这里n是G中顶点数，因此仅用O(logn)次调用算法A就可以找到G的色数。 因为我们处理的是多项式时间的算法，因此logn因子是不重要的。 2着色问题：给出一个无向图G，它是否是2可着色的？即它的顶点是否可仅用两种颜色着色，使两个邻接顶点不会分配相同的颜色？注意，当且仅当G是二分图，即当且仅当它不包含奇数长的回路时，它是2可着色的。 2可满足问题：给出一个合取范式（CNF）形式的布尔表达式f，这里每个字句恰好由两个文字组成，问f是可满足的吗？ 下面证明它是属于P类的。 由于2着色问题在P中，存在一个确定性算法A，当展示一个2可着色图时，它停机并回答yes，在展示一个图不是2可着色图时，它停机并回答no。通过在算法A中简单的交换yes和no，能够得出问题NOT-2-COLOR的一个确定性算法。这样有如下定理。 定理 10.1 P类问题在补运算下是封闭的 至于一个(不确定性)算法的运行时间，它仅仅是两个运行时间的和：一个是猜测阶段的时间；另一个是验证阶段的时间。因此它是O(ni)+ O(nj)= O(nk)，k是某个非负整数。 术语“NP完全”表示NP中判定问题的一个子类，它们在下述意义上是最难的，即如果它们中的一个被证明用多项式时间确定性算法可解，那么NP中的所有问题用多项式时间确定性算法可解，即NP=P。为了证明一个问题是NP完全的，我们需要以下定义。 定义10.4 设Π和 是两个判定问题。如果存在一个确定性算法A，它的行为如下，当给A展示问题Π的一个实例I，算法A可以把它变换为问题 的实例 ，使得当且仅当对 回答yes时，对I回答yes，而且，这个变换必须在多项式时间内完成。那么我们说Π多项式时间归约到 ，用符号 表示。 定义10.5 一个判定问题Π称为是NP困难的，如果对于NP中的每一个问题 ， 。 定义10.6 一个判定问题Π称为是NP完全的，如果下列两个条件同时成立： Π在NP问题中； 对于NP中的每一个问题 ， 。 定义 （1）对于判定问题A，若A?NP且NP中的任何一个问题可在多项式时间内归约为A，则称A为NP完全问题(NP-Complete或NPC).可以表示为A?NPC. NP完全问题类(NPC) – 定义 （2）对于判定问题A，若NP中的任何一个问题可在多项式时间归约为判定问题A，则称A为NP困难问题(NP-hard 或NPH) .可以表示为A?NPH. NPC和NP-hard两者的区别是: 验证一个问题A是否为NP-hard无须判断A是否属于NP. 根据定义可知NPC?NPH. 当已知一个问题属于NPC或NPH时，如果再遇到一个新问题： （1）若已知问题多项式归约为新问题，则新问题属于NPH; （2）若还可以验证新问题属于NP，则新问题属于NPC. 10.4.1 可满足性问题(SAT问题) 给出布尔公式f，如果它是子句的合取，我们说它是合取范式(CNF)。一个子句是文字的析取，这里文字是一个布尔变元或它的否定。一个这种公式的例子是，参考教材178