第10章 NP完全问题
主讲：王培崇
对一个已确定是可计算的问题，人们总试图寻求实现它的最优算法。然而 对有些问题，这个工作难度很大，目前还不能做到这点。
1、P类问题：问题的时间复杂性是多项式阶的，这只须设 计一个实现它的时间复杂性是多项式阶的算法即可，例如分类 （又称排序）问题。 2、顽型问题：人们已经设计出实现它的时间复杂性为指数阶 的算法，并且已证明该问题不存在多项式阶的算法，例如梵塔 问题；但是有这样一类问题， 3、NP问题：人们目前已设计的实现它的算法其时间复杂性 为指数阶的，但还不能肯定它有或没有多项式阶的算法。
如果是，则停机回答yes，如果不是则停 机回答no。
（上述是以图灵机计算模型实现的。）
• 定义10.3
NP类问题由下面的判定问题组成，对 于它们存在着多项式时间内运行的不确定性 算法。
例子10.4
coloring问题：
（1）设I是coloring的一个实例，s宣称是I的 解。容易建立一个确定性算法验证s选择、送餐车辆指派问题、车 间调度问题等。
见表1.1，现存的求解方法，中等输入也 需要几百年时间才能求解成功。
4、NP问题的描述转换 转换为判定问题。
两种答案：yes或no。 最优化问题：关心的是某个量的最大化或 最小化问题。
5、问题转化举例： 10.1设s是一个实数序列，EU问题是：是否S 中的所有的数都不相同。
判定问题：
输入：一个整数序列S； 问题：在S中存在两个数据相等吗。 10.2 给出一个无向图G=(V,E)，用k种颜色对G 着色.......，使得图中没有两个邻接点有相同的 颜色。
• 判定问题： 输入：一个无向图G=(V,E)和一个正整数k>=1； 问题：G可以k着色吗？即G最多可以用k种颜 色着色吗？
可以得出结论该问题属于NP类。
（2）建立不确定算法 对图G进行编码表示，建立并运行下面的算法A。 a、首先对于顶点集合产生一个任意颜色的指派， 猜测一个解。 b、验证该解是否合适的有效指派。 c、该解有效，停机回答yes；否则，停机回答no。
NP类与P类的区别： （1）P是一个判定问题类，这些问题可以用一个确 定性算法在多项式时间内判定或解出； （2）NP是一个判定类，这些问题可以用一个确定 性算法在多项式时间内检查或验证他们的解。
例如：求解ax2+bx+c=0；
定义10.2： 判定问题的P类由这样的判定 问题组成,他们的yes/no解可以用确定性算法 在运行多项式步数内得到。（例如：O(nk)）
• 下面问题的解都是P类问题：
1、排序问题：给出一个n个整数的表，他们 能否按非降序排列；
2、不相交集问题：给出两个整数集合，他们 的交集是否为空？
这些问题，目前根本没有找到有效解方式。（在 可以容忍的时间内解决问题。）
这些问题目前被认为是难解的。（没有确定解公 式），以后也不可能找到确定解公式。
这些难解问题，目前的求解规模在2n或n!。
• 3、这一类问题的相通性： 数百个著名的问题。
有趣的是，如果其中一个能够找到多项式 可解，那其他的问题都可以找到多项式解。
NP完全理论还很年轻，有许多问题等待人们研究。例如， “NP＝P”还是相反“P是NP的真子集”。这个问题是当代计算 机科学中的一大难题。
• 一、序言
1、 观察：前面提到的各种排序算法、图遍历算法 等，动态规划解背包等。
上述各种算法的复杂度都是在低阶多项式级别下 完成的。
2、有另外一类问题：m-图着色问题（m>2）、生 产车间调度问题、最短路径（路由）、神经网络参数 优化问题等。
如果断言解导致答案是yes，就存在一种 方法可以在多项式时间内验证这个解。
• 非确定性算法：
（1）猜测阶段：产生一个任意字符解串， 可能对应一个实例解，也可能不是。但是要 求在多项式步数内产生。
（2）验证阶段：
首先检查该字符解串，是不是合适的形 式，如果不是，停机回答no；如果是合适的 形式，则继续检查它是不是问题的实例x的解。
3、最短路径：在一个有向图G=(V,E)中，两 个特异的顶点s，t和一个整数k，在s和t之间 是否存在一条路径，它的长度最多是k。
4、2着色问题：给出一个无向图G，问它是 否可以用两种颜色着色。
如果对于任意的问题C，II的补也在C中， 我们就说问题II属于C在补运算下是封闭的。
例如：
2着色问题的补可以陈述如下：
最优化问题：求出G的着色数。 输入：一个无向图G=(V,E) 输出：G的色数。 研究NP难问题，将精力更多的投入到研 究判定问题的求解方面。
二、P类
定义10.1：设A是求解问题II的一个算法， 如果在展示问题II的一个实例时，在整个执行 过程中每一步都只有一个解，则成算法A是确 定性算法。因此，如果对于同样的输入，实 例多次执行，其输出不会改变。
1971年S. Cook发表了“The Complexity of Theorem Proving Procedures”这篇著名论文，1972年R. Karp发表了 “Reducibilty Among Combinatorial Prob1ems”，从此奠 定了NP完全理论的基础。NP完全理论指出在NP类中有一些问 题具有以下性质：若其中一个问题获得多项式算法，则这一类 问题就全部获得了多项式算法；反之，若能证明其中一个问题 是多项式时间内不可解的，则这-类问题就全部是多项式时间内 不可解的。这类问题将称之为NP完全问题。NP完全理论不打算 找出这一类问题的算法，仅仅着眼于证明这一类问题的等价性 ，即证明它们的难度相当。
给出一个图G，它是不2着色的吗？
上述问题属于P类证明：
存在一个确定算法A，当对于2可着色时， 它停机说：yes；在计算not-2着色时，它停机 说no。
对算法A进行简单的交换yes或no,可以得 出no-2算法是一个确定性算法。
三、NP类
非形式化概念：
NP类问题由这样的问题II组成，对于这 些问题存在一个确定性算法A，该算法在对II 的一个实例展示一个断言解时，它能在多项 式时间内验证解的正确性。