对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是依旧保持一样，还是也跟着慢了数百倍，或者变慢了数万倍，我们尤为关注其中随着数据量的不断增加，程序花费的时间并没有增长反而固定在某个界内，我们就说这个程序效率很好，具有$O(1)$的时间复杂度，也称常数级复杂度

还有一些穷举类算法：随着输入线性增长，算法花费时间成几何阶数上涨，这就是 $O(a^n)$ 的指数级复杂度，甚至 $O(n!)$ 的阶乘级复杂度

不会存在 $O(2n^2)$ 的复杂度，因为随着输入增加，系数并不会主要影响到程序的时间增长

我们会说 $O(0.01 \times n^3)$ 的程序的效率比 $O(100 \times n^2)$ 的效率低，尽管在 $n$ 很小的时候，前者优于后者，但后者时间随数据规模增长得慢，最终 $O(n^3)$ 的复杂度将远远超过 $O(n^2)$ 我们也说，$O(n^{100})$ 的复杂度小于 $O(1.01^n)$ 的复杂度

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

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

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

¶多项式级算法是万能的吗

❓是否所有的问题都可以找到复杂度为多项式级的算法呢？

答案是否定的，有些问题甚至根本不可能找到一个正确的算法，这称之为不可解问题(Undecidable Decision Problem)，停机问题就是一个著名的不可解问题

halting problem 是逻辑数学中可计算性理论的一个问题，停机问题是：判断任意一个程序是否能在有限的时间之内结束运行，该问题等价于如下的判定问题：是否存在一个程序 P，对于任意输入的程序 w，能够判断 w 会在有限时间内结束或者陷入死循环
艾伦-图灵在 1936 年用对角论证法证明了，不存在解决停机问题的通用算法

¶p 类问题

❓什么是 P 类问题

如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于 P 问题

¶NP 问题

❓什么是 NP 问题？

NP 问题不是非 P 类问题。NP 问题是指可以在多项式的时间里验证一个解的问题。NP 问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。

例如：你是一个lucky dog，在程序中需要枚举时，可以一猜一个准，某人拿到了一个求最短路径的问题，问从起点到终点是否有一条小于 100 个单位长度的路线。它根据数据画好了图，但怎么也算不出来，于是来问你：如何选条路走得最少？你运气很好，肯定能随便指条很短的路出来。然后你就胡乱画了几条线，说就这条吧。那人按你指的这条把权值加起来一看，嘿，神了，路径长度 98，比 100 小。于是答案出来了，存在比 100 小的路径。别人会问他这题怎么做出来的，他就可以说，因为找到了一个比 100 小的解。

在这个题中，找一个解很困难，但验证一个解很容易。验证一个解只需要$O(n)$的时间复杂度，也就是说我可以花$O(n)$的时间把我猜的路径的长度加出来。那么，只要我运气好，猜得准，我一定能在多项式的时间里解决这个问题。我猜到的方案总是最优的，不满足题意的方案也不会来骗我去选它，满足这类问题就是 NP 问题

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

例如：前面所说的 Hamilton 回路是 NP 问题，因为验证一条路是否恰好经过了每一个顶点非常容易。但我要把问题换成这样：试问一个图中是否不存在 Hamilton 回路。这样问题就没法在多项式的时间里进行验证了，因为除非你试过所有的路，否则你不敢断定它没有 Hamilton 回路

🤔定义 NP 问题，是因为通常只有 NP 问题才可能找到多项式的算法，我们不会指望一个连多项式验证一个解都不行的问题，存在一个解决它的多项式级的算法

信息学中的号称最困难的问题——NP 问题，实际上是在探讨 NP 问题与 P 类问题的关系

很显然，所有的 P 类问题都是 NP 问题。也就是说，能多项式地解决一个问题，必然能多项式地验证一个问题的解。人们想知道，是否所有的 NP 问题都是 P 类问题。如果把所有 P 类问题归为一个集合$\mathbb{p}$中，把所有 NP 问题划进另一个集合$\mathbb{N}_p$中，那么，显然有$\mathbb{p} \subseteq \mathbb{N}_p$

✨现在，所有对 NP 问题的研究都集中在一个问题上：$\mathbb{P} =\mathbb{N}_p$？

通常所谓的NP 问题，其实就一句话：证明或推翻 $\mathbb{P} =\mathbb{N}_p$

目前为止这个问题还并不知道答案，但是，存在一个大方向，人们普遍认为，$\mathbb{P} =\mathbb{N}_p$不成立。也就是说，多数人相信，存在至少一个不可能有多项式级复杂度的算法的 NP 问题。人们如此坚信$\mathbb{P} \neq\mathbb{N}_p$是有原因的。就是在研究 NP 问题的过程中找出了一类非常特殊的 NP 问题叫做NP-完全问题，也即所谓的 NPC 问题。正是 NPC 问题的存在，使人们相信$\mathbb{P} \neq\mathbb{N}_p$

¶NPC 问题

为了说明 NPC 问题，我们先引入一个概念——约化(Reducibility，有的资料上叫归约)

¶归约

简单地说，一个问题 A 可以约化为问题 B 的含义是：可以用问题 B 的解法解决问题 A，或者说，问题 A 可以变成问题 B

现在有两个问题：求解一个一元一次方程和求解一个一元二次方程。那么我们说，前者可以约化为后者，意即知道如何解一个一元二次方程那么一定能解出一元一次方程。我们可以写出两个程序分别对应两个问题，那么我们能找到一个“规则”，按照这个规则把解一元一次方程程序的输入数据变一下，用在解一元二次方程的程序上，两个程序总能得到一样的结果
Thomas H.Cormen ...《算法导论》

这个规则即是：两个方程的对应项系数不变，一元二次方程的二次项系数为 0。按照这个规则就把前一个问题转换成后一个问题，两个问题就等价了。同样地，我们可以说，Hamilton 回路可以约化为 TSP 问题(Travelling Salesman Problem，旅行商问题)：在 Hamilton 回路问题中，两点相连即这两点距离为 0，两点不直接相连则令其距离为 1，于是问题转化为在 TSP 问题中，是否存在一条长为 0 的路径。Hamilton 回路存在当且仅当 TSP 问题中存在长为 0 的回路

问题 A 可约化为问题 B 有一个重要的直观意义：B 的时间复杂度高于或者等于 A 的时间复杂度，也就是说，问题 A 不比问题 B 难。这很容易理解。既然问题 A 能用问题 B 来解决，倘若 B 的时间复杂度比 A 的时间复杂度还低了，那 A 的算法就可以改进为 B 的算法，两者的时间复杂度还是相同。正如解一元二次方程比解一元一次方程难，因为解决前者的方法可以用来解决后者

很显然，约化具有一项重要的性质：约化具有传递性，如果问题 A 可约化为问题 B，问题 B 可约化为问题 C，则问题 A 一定可约化为问题 C

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

这里所说的可约化是指可多项式地约化(Polynomial-time Reducible)，即变换输入的方法是能在多项式的时间里完成的，约化的过程只有用多项式的时间完成才有意义

从约化的定义中我们看到，一个问题约化为另一个问题，时间复杂度增加了，问题的应用范围也增大了。通过对某些问题的不断约化，我们能够不断寻找复杂度更高，但应用范围更广的算法来代替复杂度低，但应用范围小的算法

❓再回想前面讲的 P 和 NP 问题，联想起约化的传递性，自然地，我们会想问，如果不断地约化上去，不断找到能归纳若干小 NP 问题的一个稍复杂的大 NP 问题，那么最后是否有可能找到一个时间复杂度最高，并且能归纳所有 NP 问题的这样一个超级 NP 问题？

答案居然是肯定的，存在这样一个 NP 问题，所有的 NP 问题都可以约化成它。换句话说，只要解决了这个问题，那么所有的 NP 问题都解决了。这种问题的存在难以置信，并且更加不可思议的是，这种问题不只一个，它有很多个，它是一类问题。这一类问题就是传说中的NPC 问题，也就是NP-完全问题

📓NPC 问题的出现使整个 NP 问题的研究得到了飞跃式的发展。我们有理由相信，NPC 问题是最复杂的问题。再次回到全文开头，人们想表达一个问题不存在多项式的高效算法时应该说它属于 NPC 问题

¶NPC 定义

❓什么样的问题是一个 NPC 问题？

它是一个 NP 问题
所有的 NP 问题都可以约化到它

证明一个问题是 NPC 问题也很简单。先证明它至少是一个 NP 问题，再证明其中一个已知的 NPC 问题能约化到它（由约化的传递性，则 NPC 问题定义的第二条也得以满足），这样就可以说它是 NPC 问题了

既然所有的 NP 问题都能约化成 NPC 问题，那么只要任意一个 NPC 问题找到了一个多项式的算法，那么所有的 NP 问题都能用这个算法解决了，NP 也就等于 P 了

因此，前文说，正是 NPC 问题的存在，使人们相信$\mathbb{P} \neq \mathbb{N}_p$。可以直观地理解，NPC 问题目前没有多项式的有效算法，只能用指数级甚至阶乘级复杂度的搜索

¶NP-Hard

❓NP-Hard 问题是什么？

满足 NPC 问题定义的第二条但不一定要满足第一条（就是说，NP-Hard 问题要比 NPC 问题的范围广）

NP-Hard 问题同样难以找到多项式的算法，但它不列入我们的研究范围，因为它不一定是 NP 问题。即使 NPC 问题发现了多项式级的算法，NP-Hard 问题有可能仍然无法得到多项式级的算法。事实上，由于 NP-Hard 放宽了限定条件，它将有可能比所有的 NPC 问题的时间复杂度更高从而更难以解决。

¶NPC 举例

🤔证明一个问题是否是 NPC 问题时，需要一个 NPC 问题能够约化到这个问题来证明，那么第一个 NPC 问题是如何出现的？

逻辑电路问题，这是第一个 NPC 问题。其它的 NPC 问题都是由这个问题约化而来的。因此，逻辑电路问题是 NPC 类问题的鼻祖

❓什么是逻辑电路问题？

逻辑电路问题是指的这样一个问题：给定一个逻辑电路，问是否存在一种输入使输出为 True
它显然属于 NP 问题，并且可以直接证明所有的 NP 问题都可以约化到它。证明过程的大概意思是说任意一个 NP 问题的输入和输出都可以转换成逻辑电路的输入和输出，因此对于一个 NP 问题来说，问题转化为了求出满足结果为 True 的一个输入，即一个可行解

有了第一个 NPC 问题后，一大堆 NPC 问题就出现了，因为再证明一个新的 NPC 问题只需要将一个已知的 NPC 问题约化到它就行了。后来，Hamilton 回路成了 NPC 问题，TSP 问题也成了 NPC 问题。现在被证明是 NPC 问题的有很多，任何一个找到了多项式算法的话所有的 NP 问题都可以完美解决了

¶总结

本文的核心都在下面这张图里面了

¶附录

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

计算复杂性

目录

¶时间复杂度