【原】谈一谈|如何理解NP问题

算法与编程之美 2020-10-30

展开全文

一概念引入

1.1时间复杂度

在计算机处理一个问题时，往往需要一定的时间，假设把这个问题复杂化（将这个问题进行扩展），那么把计算机处理这类问题的时间变化速率，称为解决这种问题所用算法的时间复杂度。例如，一个枚举一定范围内的数字的问题，计算机所用时间会随着范围的变化而线性变化，由于是简单的枚举，所以时间复杂度可以记为O(n)，n可以代表这个范围大小。在计算机处理问题时，由于算法设计不同，对应的时间复杂度也不一定相同。

1.2多项式级时间和非多项式级时间

在众多的时间复杂度中，根据其表达式的特点，可以大致将它们划分为两个范畴，一个是多项式级一个是非多项式级。它们各自表示什么意思呢？还记得高中数学中学习的函数吗，在学习不同函数时，最常做的一件事是观察它们的图像变化，可以发现，x作为底数的图像和x作为指数的图像在后期的变化简直有天壤之别。这也正是需要将时间复杂度划分的原因（多项式级的时间复杂度在后期变化远小于非多项式级），将n作为底数的时间复杂度归为多项式级，n作为指数的归为非多项式级。例如O(n)、O(log(n))、O(n^a)等就是多项式级的时间复杂度，像O(n!)和O(a^n)就是非多项式级的复杂度。对于计算机来说需要处理的问题往往是很庞大的，如果采用非多项式级复杂度的算法，那么将浪费很大的资源。

1.3 P问题

在解释了多项式级和非多项式级时间复杂度之后，P问题的概念就简单了。对于众多的问题，通常把能够使用多项式级时间复杂度算法解决的问题称为P问题。

二什么叫NP问题

2.1 约化

一般，问题A可以约化为问题的B的解释是可以用解决问题B的方法解决问题A。简单的说，也就是问题A是问题B的另一种形式，且问题A的复杂程度要小于等于问题B。就像解方程组的问题，假如你会解二元一次方程组，那么你一定会解一元一次方程，在这个例子中，一元一次方程就是问题A，二元一次方程组就是问题B，问题A可以看作是问题B中另一个自变量系数为零的特殊“二元一次方程组”。那么解二元一次方程组的问题是否可以约化成解三元一次方程组问题呢？答案很明显是可以，同理的，解一元一次方程也可以约化成解三元一次方程组问题。可以看出，约化是具有传递性的，且如果问题A可以约化成问题B，则问题B的时间复杂度一定大于等于问题A的时间复杂度。

2.2 P=NP？

有了约化这个概念之后，可以发现所有的P问题都可以约化成NP问题。因为一个问题既然可以在多项式级时间内解决，那么对于验证一个解的正确性是肯定可以做到的，因此，如果把P问题看作一个集合P，NP问题看作另一个集合NP，则P包含于NP。那么P=NP吗？答案尚未确定，这也是现在所常研究的“NP问题”的实质，这是一道世界难题，一旦解决这个问题，那么就意味着可以找出具有多项式级时间复杂度的算法来解决NP问题。

三新的问题

3.1 NP与NPC问题

前文提到确定P=NP的问题是一道世界难题，这是因为已知的NP问题远远多于P问题，且运用约化的概念，是否所有的NP问题也可以约化成同一个问题呢？这个问题的答案早已被证实是可行的，而且这种问题还不止一个，它们被称为NPC问题。很明显，NPC问题具有两个特点：它满足NP问题的条件，且所有的NP问题都可以约化成它。既然所有的NP问题都可以约化成NPC问题，那么只要能够在多项式级的时间复杂度下解决一个NPC问题，所有的NP问题也都能用同样的方法解决了，那么NP问题也就成了P问题。但是给一个NPC问题找出一个多项式级时间复杂度的算法的工作至今仍在进行中，因此，还是很难证明P=NP。

3.2 NPC案例

逻辑电路是一个典型的NPC问题，什么叫做逻辑电路呢？一个逻辑电路由若干个输入，一个输出，若干“逻辑门”和密密麻麻的线组成。在逻辑电路问题中，需要找到不同输入的组合，使得输出的结果满足要求。

图3.1.1 逻辑电路示意图

逻辑电路之所以是一个NPC问题，是因为你无法在多项式级的时间复杂度内解决它，但是要想验证一个解的正确性是很简单的，无论这个逻辑电路多么复杂，仍然只需要将每个点的状态带入进去就可以验证，属于O(n)的时间复杂度。

3.3 NPC与NP-Hard问题

NP-Hard问题和NPC问题的不同在于NP-Hard问题不一定是NP问题，因此，NP-hard问题的范围要大于NPC问题，同时，要为NP-Hard问题找到一个多项式级时间复杂度的算法也更加困难，这也是“Hard”的含义，可能NPC问题能够找到多项式级时间复杂度算法的时候NP-Hard问题仍然还无法完成这项工作。

四 P、NP、NPC、NP-Hard问题的关系

在上述介绍中，可以知道，P问题包含于NP问题中，NPC问题同时包含于NP问题和NP-Hard问题，也就是它们的交集，则它们的关系可以如下表示。