1000字范文 > P NP NPC NP-Hard等问题总结

P NP NPC NP-Hard等问题总结

时间：2021-09-04 03:24:21

0.概念

P Problem: 对于任意的输入规模 n，问题都可以在 n 的多项式时间内得到解决；NP(Non-deterministic Polynomial) Problem: 可以在多项式的时间里验证一个解的问题；NPC(Non-deterministic Polynomial Complete) Problem: 满足两个条件: 是一个 NP 问题所有的 NP 问题都可以约化到它NP-hard Problem: 满足NPC问题的第 2 条，但不一定要满足第 1 条。（NP-Hard问题要比 NPC问题的范围广）

1. P Problem

如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于 P 问题，即算法的时间复杂度是多项式级的。比如 n 个数中间找到最大值，或者 n 个数排序之类的。

2. NP Problem

NP 问题的另一个定义是可以在多项式的时间里猜到一个解的问题，例如求图中起点到终点是否有一条小于100个单位长度的路线，随便选一条，如果算出来路径小于100，那么就猜到了一个解，也就是说如果你运气足够好的话就可以在多项式时间内解决这个问题。当然猜的前提是问题存在解。

很显然，所有的 P 类问题都是 NP 问题，能在多项式时间内解决，必然能多项式地验证一个解。（NP 是否等于 P 这个问题貌似还没有定论。）

著名的NP类问题：旅行家推销问题(TSP)。

有一个推销员，要到 n 个城市推销商品，他要找出一个包含所有 n 个城市的环路，这个环路路径小于 a 。我们知道这个问题如果单纯的用枚举法来列举的话会有 ( n − 1 ) ! 种，已经不是多项式时间的算法了(注：阶乘算法比多项式的复杂)。那怎么办呢？我们可以用猜的，假设我人品好，猜几次就猜中了一条小于长度 a 的路径，好的，我得到了一条路径小于 a 的环路，问题解决了，皆大欢喜。可是，我不可能每次都猜的那么准，也许我要猜完所有种呢？所以我们说，这是一个 NP 类问题。

所以这就引出了这类讨论的一个千年问题：是否 NP类问题=P类问题？即是否所有能在多项式时间内验证得出正确解的问题，都是具有多项式时间算法的问题呢？要是解决了这个问题，那岂不是所有的NP问题都可以通过计算机来解决。

3. NPC Problem

存在一个NP问题，使得所有的该类NP问题都可以多项式时间地规约(Polynomial-time Reducibility) 为NPC问题。根据规约的传递性，对NP问题进行一层接一层地规约，最终可以得到一个足够泛化的NP问题，即NPC问题。

什么是约化 (Reducibility)

一个问题 A 可以约化为问题 B 的含义是，可以用问题B的解法解决问题A。（个人感觉是说，问题 A 是 B 的一种特殊情况。）标准化的定义是，如果能找到一个变化法则，对任意一个 A 程序的输入，都能按照这个法则变换成 B 程序的输入，使两程序的输出相同，那么问题 A 可以约化为问题 B 。

例如求解一元一次方程这个问题可以约化为求解一元二次方程，即可以令对应项系数不变，二次项的系数为0，将A的问题的输入参数带入到B问题的求解程序去求解。另外，约化还具有传递性，A 可以化约为 B，B 可以约化为 C，那么 A 也可以约化为 C。

4. NP-hard 问题

NP-hard problem, NP(Non-deterministic Polynomial)

5.其它

5.1 什么是时间复杂度（Time Complexity）

时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有O(1)的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是O(n)，比如找n个数中的最大值；而像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，属于的复杂度。还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是的指数级复杂度，甚至O(n!)的阶乘级复杂度。不会存在的复杂度，因为前面的那个“2”是系数，根本不会影响到整个程序的时间增长。同样地，的复杂度也就是的复杂度。因此，我们会说，一个的程序的效率比的效率低，尽管在n很小的时候，前者优于后者，但后者时间随数据规模增长得慢，最终的复杂度将远远超过。我们也说，的复杂度小于的复杂度。

容易看出，前面的几类复杂度被分为两种级别，其中后者的复杂度无论如何都远远大于前者;一种是,,等，我们把它叫做多项式级的复杂度，因为它的规模n出现在底数的位置；另一种是和型复杂度，它是非多项式级的，其复杂度计算机往往不能承受。当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，往往会超时，除非是数据规模非常小。

O()和o()分别代表同阶无穷小和高阶无穷小.
a,b都是无穷小．
如果b/a的极限等于0,就说b是比a高阶的无穷小,记作b=o(a).
如果b/a的极限等于c(c≠0),就说b与a是同阶无穷小,记作b=O(a)

5.2 什么是启发式算法

启发式算法一般用于解决NP-hard问题，其中NP是指非确定性多项式。

例如，著名的推销员旅行问题（Travel Saleman Problem or TSP）：假设一个推销员需要从南京出发，经过广州，北京，上海，…，等 n 个城市，最后返回香港。任意两个城市之间都有飞机直达，但票价不等。假设公司只给报销 C 元钱，问是否存在一个行程安排，使得他能遍历所有城市，而且总的路费小于 C？

推销员旅行问题显然是 NP 的。因为如果你任意给出一个行程安排，可以很容易算出旅行总开销。但是，要想知道一条总路费小于 C 的行程是否存在，在最坏情况下，必须检查所有可能的旅行安排。

启发式算法是相对于最优化算法提出的，是基于直观或者经验构造的算法，在可接受的开销（时间和空间）内给出待解决组合优化问题的一个可行解。