什么是P，NP和NPC问题？

• 2020 年 8 月 14 日
• 笔记

P问题，NP问题，NPC问题？这些都是计算机科学领域，关于算法方面的术语。在认识这些术语之前，建议同学们先认真学习一下算法的时间复杂度，因为算法的时间复杂度与P，NP和NPC问题高度相关。

什么是P问题？

P是英文单词Polynomial的首字母，多项式的意思。

如果问题可以通过一个多项式复杂度的算法解决，这个问题就可以称为P问题。多项式复杂度意味着，算法的计算量在一个可以接受的范围内，我们很容易就能得到计算结果。如果是指数级复杂度的算法，有可能在问题规模达到一定级别的时候，就更本算不出来。

什么是NP问题？

NP的全称为 Non-deterministic Polynomial，而不是Non-Polynomial。所以，NP问题并不是非P问题。

NP问题是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。Non-deterministic Polynomail直译的意思是，不是确定的多项式，即不确实是否是P问题。如果能够找到一个多项式复杂度级别的算法，那么这个问题就是P问题，如果找不到，但是可以在多项式复杂度级别的情况下验证，就是NP问题。

网上看到一个牛人写的例子，用来理解NP问题：

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

P问题肯定是NP问题，因为P问题有多项式复杂度级别的算法来解，就一定能在多项式复杂度级别的情况下验证。

再来一个理解NP问题的例子：

给出 n 个城市和两两之间的距离，求找到一个行走方案，使得到达每个城市一次的总路程最短。我们可以这样来“猜测”它的解：先求一个总路程不超过 100 的方案，假设我们可以依靠极好的运气“猜出”一个行走路线，使得总长度确实不超过 100，那么我们只需要每次猜一条路一共猜 n 次。接下来我们再找总长度不超过 50 的方案，找不到就将阈值提高到75…… 假设最后找到了总长度为 90 的方案，而找不到总长度小于 90 的方案。我们最终便在多项式时间内“猜”到了这个旅行商问题的解是一个长度为 90 的路线。它是一个 NP 类的问题。

也就是说，NP 问题能在多项式时间内“解决”，只不过需要好运气。显然，P 类问题肯定属于 NP 类问题。

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

之所以要定义NP问题，是因为通常只有NP问题才可能找到多项式的算法。我们不会指望一个连在多项式复杂度情况下验证一个解都不行的问题，存在一个解决它的多项式复杂度级的算法。信息学中的号称最困难的问题——“NP问题”，实际上是在探讨NP问题与P类问题的关系，即 \(P=NP\) ，还是 \(P≠NP\) 。

什么是NPC问题？

NPC就是NP完全问题，C是Complete的首字母。

为了说明NPC问题，我们先引入一个概念：约化（Reducibility，化简的能力，有的资料上叫“归约”）。

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

《算法导论》上举了这么一个例子。比如说，现在有两个问题：求解一个一元一次方程和求解一个一元二次方程。那么我们说，前者可以约化为后者，意即知道如何解一个一元二次方程那么一定能解出一元一次方程。我们可以写出两个程序分别对应两个问题，那么我们能找到一个“规则”，按照这个规则把解一元一次方程程序的输入数据变一下，用在解一元二次方程的程序上，两个程序总能得到一样的结果。这个规则即是：两个方程的对应项系数不变，一元二次方程的二次项系数为0。按照这个规则把前一个问题转换成后一个问题，两个问题就等价了。

再来一个约化的例子：

在与数不尽的问题搏斗的过程中，人们有时候会发现，解决问题 A 的算法可以同时用来解决问题 B。例如问题 A 是对学生的姓名与所属班级同时排序，问题 B 是对人们按照姓名做排序。这时候，我们只需要让班级全都相同，便能照搬问题 A 的算法来解决问题 B。这种情况下，数学家就说，问题 B 能归约为问题 A。

“问题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），即变换输入的方法是能在多项式的时间里完成的。约化的过程只有用多项式的时间完成才有意义。

从约化的定义中我们看到，一个问题约化为另一个问题，时间复杂度增加了，问题的应用范围也增大了。通过对某些问题的不断约化，我们能够不断寻找复杂度更高，但应用范围更广的算法来代替复杂度虽然低，但只能用于很小的一类问题的算法。联想起约化的传递性，自然地，我们会想问，如果不断地约化上去，不断找到能“通吃”若干小NP问题的一个稍复杂的大NP问题，那么最后是否有可能找到一个时间复杂度最高，并且能“通吃”所有的 NP问题的这样一个超级NP问题？

答案居然是肯定的。也就是说，存在这样一个NP问题，所有的NP问题都可以约化成它。换句话说，只要解决了这个问题，那么所有的NP问题都解决了。这种问题的存在难以置信，并且更加不可思议的是，这种问题不只一个，它有很多个，它是一类问题。这一类问题就是传说中的NPC问题，也就是NP完全问题。如果我们给其中任何一个NPC问题找到了多项式级别的算法，就相当于证明了 \(P=NP\)。但是人们至今没有成功找到。

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

既然所有的NP问题都能约化成NPC问题，那么只要任意一个NPC问题找到了一个多项式的算法，那么所有的NP问题都能用这个算法解决了，\(NP=P\) 。因此，给NPC找一个多项式算法太不可思议了。因此，正是NPC问题的存在，使人们倾向于相信 $P≠NP $。我们可以就此直观地理解，NPC问题目前没有多项式的有效算法，只能用指数级甚至阶乘级复杂度的搜索。

这部分最后，NPC问题的定义。同时满足下面两个条件的问题就是NPC问题。

首先，它得是一个NP问题；

然后，所有的NP问题都可以约化到它。

有了第一个NPC问题后，一大堆NPC问题就出现了，因为再证明一个新的NPC问题只需要将一个已知的NPC问题约化到它就行了。

实在太抽象了。。。。

NP-Hard问题

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

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

以上问题反复阅读几次，相信足够理解什么是P问题，什么是NP问题，什么NPC问题。