什么是P问题、NP问题和NPC问题

时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。

也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率并不能衡量一个程序的好坏，而是应当看当数据规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着变慢了数百倍，或者变慢了数万倍。

• 不管数据有多大，程序处理时间始终不变，具有O(1)的时间复杂度，也称常数级复杂度。
• 数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是O(n)。比如说从n个数中找最大值。
• 而像冒泡排序，插入排序等，数据扩大两倍，时间变慢四倍，属于O(n²)的复杂度。
• 还有一些穷举类的算法，所需时间成几何阶数上涨，也就是O(aⁿ)的指数级复杂度，甚至是O(n!)。

以上几类复杂度被分为两种级别，其中后者的复杂度无论如何都远远大于前者。

• 一种是O(1)，O(log(n))，O(n^a)等，我们把它叫做多项式级的复杂度，因为它的规模n出现在底数的位置。
• 另一种是O(aⁿ)和O(n!)型复杂度，它是非多项式级别的，其复杂度往往是计算机不能承受。

当我们选择一个问题时，选择的算法通常都是多项式级别的复杂度，非多项式级别的复杂度需要的时间太多，往往会超时，除非是数据规模非常小。

不可解问题

有些问题找不到复杂度为多项式级的算法，称为“不可解问题”（Undecidable Decision Problem）。

Hamiton回路：给你一个图，能否找到一条经过每个顶点一次且恰好一次，最后又走回去的路。这个问题就没有找到多项式级的算法。

P类问题

如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题属于P问题。P是英文单词多项式的第一个字母。

NP问题

NP问题不是非P类问题。
NP问题指可以在多项式的时间里验证一个解的问题/可以在多项式的世界里猜出一个解的问题。

• 比如说，我RP很好，在程序中需要枚举时，我可以一猜一个准。
• 现在某人拿到了一个求最短路径的问题，问从起点到终点是否有一条小于100个单位长度的路线。它根据数据画好了图，但怎么也算不出来，于是来问我：你看怎么选条路走得最少？
• 我说，我RP很好，肯定能随便给你指条很短的路出来。然后我就胡乱画了几条线，说就这条吧。那人按我指的这条把权值加起来一看，嘿，神了，路径长度98，比100小。于是答案出来了，存在比100小的路径。
• 别人会问他这题怎么做出来的，他就可以说，因为我找到了一个比100 小的解。
• 在这个题中，找出一个解很困难，但验证一个解很容易。验证一个解只需要O(n)的时间复杂度，也就是说我可以花O(n)的时间把我猜的路径的长度加出来。
• 那么，只要我RP好，猜得准，我一定能在多项式的时间里解决这个问题。我猜到的方案总是最优的，不满足题意的方案也不会来骗我去选它。这就是NP问题。

当然也有不是NP问题的问题，你猜到了解但是没用，因为不能在多项式的时间里去验证它。

• 很显然，前面所说的Hamiton回路是NP问题，因为验证一条路是否恰好经过了每一个顶点非常容易。
• 但把问题换为一个图中是否不存在Hamiton回路，就没办法在多项式的时间里验证了，因为除非试过所有的路，否则无法断定“没有Hamiton回路”。

**所有的P类问题都是NP问题。**也就是说，能多项式解决一个问题，必然能多项式地验证一个问题的解。

但人们普遍相信，存在一个不可能有多项式级复杂度的算法的NP问题。

NPC问题（NP-完全问题）

约化
一个问题A可以约化为问题B的含义是：可以用问题B的解法解决问题A。
但B的时间复杂度一定要高于或者等于A的时间复杂度。

约化具有传递性：问题A可以约化为问题B，问题B可以约化为问题C，问题A可以约化为问题C。

**约化的标准概念：**如果能找到一个变化法则，对任意一个程序A的输入，都能按这个法则变换成程序B的输入，使两程序的输出相同，那么可以说，问题A可以约化为问题B。

NPC问题定义

1. 首先，是一个NP问题。
2. 所有NP问题都可以约化到它。

证明一个问题是NPC问题

• 先证明它至少是一个NP问题。
• 再证明其中一个已知的NPC问题能约化到它。

既然所有的NP问题都能约化成NPC问题，那么只要任意一个NPC问题找到了一个多项式的算法，那么所有的NP问题都能用这个算法解决了，NP就等于P了。
但目前NPC问题没呀多项式的有效算法，只能用指数级甚至阶级乘复杂度的搜索。

NP-Hard问题

NP-Hard问题满足NPC问题定义的第二条，但不满足第一条。