关于算法NP、NPC、NPhard问题调研

本次新生研讨课上，老师向我们介绍了算法与复杂性有关问题，讲解了一些简单算法，并用U盘装程序的实际问题，向我们科普了NPhard问题。对于这个算法的前沿问题，我虽然不能深入理解，但还是怀着兴趣进行了一下调研。

1. 从时间复杂度出发

时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。

如果不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有O(1)的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是O(n)，比如找n个数中的最大值；而像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，属于O(n^2)的复杂度。还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是O(a^n)的指数级复杂度，甚至O(n!)的阶乘级复杂度。不会存在O(2n^2)的复杂度，因为前面的那个“2”是系数，根本不会影响到整个程序的时间增长。同样地，O (n^3+n^2)的复杂度也就是O(n^3)的复杂度。因此，我们会说，一个O(0.01n^3)的程序的效率比O(100*n^2)的效率低，尽管在n很小的时候，前者优于后者，但后者时间随数据规模增长得慢，最终O(n^3)的复杂度将远远超过O(n^2)。我们也说，O(n^100)的复杂度小于O(1.01^n)的复杂度。

2. P问题

自然地，会想到一个问题：会不会所有的问题都可以找到复杂度为多项式级的算法呢？答案是否定的。如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。

3. NP 问题

NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。举个例子：我人品很好，在程序中需要枚举时，我可以一猜一个准。

现在某人拿到了一个求最短路径的问题，问从起点到终点是否有一条小于100个单位长度的路线。它根据数据画好了图，但怎么也算不出来，于是来问我：你看怎么选条路走得最少？

我说，我人品很好，肯定能随便给你指条很短的路出来。然后我就胡乱画了几条线，说就这条吧。那人按我指的这条把权值加起来一看，路径长度98，比100小。于是答案出来了，存在比100小的路径。别人会问他这题怎么做出来的，他就可以说，因为我找到了一个比100 小的解。在这个题中，找一个解很困难，但验证一个解很容易。验证一个解只需要O(n)的时间复杂度，也就是说我可以花O(n)的时间把我猜的路径的长度加出来。那么，只要我RP好，猜得准，我一定能在多项式的时间里解决这个问题。这就是NP问题。

4. NPC问题

NP-C（Complete）问题满足两个条件：

首先它是一个NP问题
所有的NP问题都可以约化到它，NPC问题目前没有多项式的有效算法，只能用指数级甚至阶乘级复杂度的搜索
约化：例如，求解一个一元一次方程 A AA 和求解一个一元二次方程 B BB，你若会求解 B BB ，你一定会求解 A AA。那么我们说，A 可以约化为 B。B BB 的时间复杂度高于或者等于 A AA的时间复杂度。

5. NPhard问题

NPhard问题不一定是一个NP问题，即使 NPC 问题发现了多项式级的算法，NP-Hard 问题有可能仍然无法得到多项式级的算法。例如U盘装程序问题，只能用贪心的方法找的它的近似解。但它更加未知，将有可能比所有的 NPC 问题的时间复杂度更高从而更难以解决。