浅谈P、NP、NP-Complete和NP-Hard问题

发表于 2023-09-13 更新于 2024-08-08 阅读次数：

来自：浅谈P、NP、NP-Complate和NP-Hard问题

多项式级时间复杂度与非多项式级时间度

时间复杂度

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

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

不管数据有多大，程序处理所花的时间始终是那么多的，我们就说这个程序很好，具 \(O(1)\) 的时间复杂度，也称常数级复杂度；

数据规模变得有多大，花的时间也跟着变得有多长，比如找n个数中的最大值这个程序的时间复杂度就是\(O(n)\)，为线性级复杂度，

而像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，时间复杂度是\(O(n^2)\)，为平方级复杂度。

还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是\(O(a^n)\)的指数级复杂度，甚至\(O(n!)\)的阶乘级复杂度。

多项式级时间复杂度

像\(O(1), O(ln(n)), O(n^a)\)等，我们把它叫做多项式级时间复杂度，因为它的规模n出现在底数的位置；

非多项式级时间时间度

另一种像是 \(O(a^n)\) 和 \(O(n!)\) 等，是非多项式级的时间复杂度，其复杂度计算机往往不能承受。

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

P问题与NP问题

P问题

能在多项式时间内解决的问题。

例如，计算1-1000的连续整数之和：这个问题就比较简单，无论是编程还是使用高斯求和公式都可以在有限可接受的时间内完成，这种算是P类问题。

NP问题

指一个复杂问题不能确定是否在多项式时间内找到答案，但是可以在多项式时间内验证答案是否正确。 即能在多项式时间内验证得出一个正确解的问题。

例如，计算地球上所有原子个数之和：这个问题就很困难甚至无解，但是现在有个答案是300个，显然是错的，所以很容易验证但不容易求解，这种算NP类问题。

P问题与NP问题的关系

如果一个问题是P问题，那么毫无疑问我们可以在多项式时间内验证它。

P类问题是可以在多项式时间内解决并验证的一类问题，NP类问题是可以多项式时间验证但是不确定能否在多项式时间内解决的一类问题。 \[ P \subseteq NP \]

NP-Complete(NPC)问题

这个问题需要满足两个条件:

它是一个NP问题
其他所有属于NP的问题都可以规约成它

换句话说，只要解决了这个问题，那么所有的NP问题都解决了。

可归约：就是将一个问题转化为另一个问题，使的用第二个问题的解来解第一个问题第一个问题。这种思想类似于数学证明中，如果一个证明很难从原命题切入，此时根据原命题与其逆否命题是等价的，将原命题转换成逆否命题求解，将得到及其简便的解法或者是结题的切入点。例如，假设要在一个城市中认路，如果有一张地图，就将认路问题归约得到地图问题。

同时约化还具有一个重要性质：约化具有传递性。也就是说如果问题A可约化为问题B，问题B可约化为问题C，那么问题A一定可约化为问题C。

NP-Hard问题

它满足NPC问题定义的第二条但不一定要满足第一条。即所有的NP问题都能约化到它，但是他不一定是一个NP问题。

NP-Hard问题同样难以找到多项式的算法，但它不列入我们的研究范围，因为它不一定是NP问题。即使NPC问题发现了多项式级的算法，NP-Hard问题有可能仍然无法得到多项式级的算法。

事实上，由于NP-Hard放宽了限定条件，它将有可能比所有的NPC问题的时间复杂度更高从而更难以解决。

NPC与NP-Hard的典型示例-旅行推销员问题

旅行推销员问题（Traveling Salesman Problem, TSP） 是一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。

旅行商问题有两个版本：

在一个图里，除了起始点以外不重复地遍历所有节点构成一条闭合回路，问这条回路的最短路径是多少？（应如何选择行进路线，以使总的行程最短）---这个是最优解问题
在一个图里，除了起始点以外不重复地遍历所有节点构成一条闭合回路，问路径长度小于等于某个值的这样的回路是否存在？（应如何选择行进路线，以使总的行程小于等于某个值）---这个是判定性问题

对于问题1，是无法令确定型图灵机在多项式时间内验证答案的，所以问题1不是NP问题，因此也不是NPC问题，但是Hamilton回路问题可以约化为TSP问题，而Hamilton回路问题是NP问题，因此是NP-Hard问题。

对于问题2，可以令确定型图灵机在多项式时间内验证答案，所以问题2是NP问题，同时Hamilton回路问题可以约化为TSP问题，而Hamilton回路问题是NP问题，因此问题2是NP-Hard问题，同时它也是NPC问题。

P=NP?

来自 https://zhuanlan.zhihu.com/p/141884913

P 是否等于 NP。早在 2000 年 5 月的时候，Clay Institute 将这个问题列为了数学里的七大千禧问题之一，如果有人能证明出 P = NP 或 P ≠ NP，就会获得该机构整整 100 万美元的奖金。并且一旦证明出 P = NP 将会改变现有人类所有的知识体系，下面我们就来看看这个问题到底在讲什么吧。

1694747131453

P 问题与 NP 问题

首先我们要知道什么是 P 问题和 NP 问题，所谓的 P 问题就是能够在多项式的时间复杂度内解决的问题，这里的 P 指的是多项式时间（polynomial time）的意思。比如排序问题，二分查找，图的遍历，最小生成树等。

对于那些不能在多项式的时间复杂度内解决的问题，比如说背包问题，分配问题等等，我们会认为这个问题很难，可能需要在指数或阶乘的时间复杂度内解决，但是如果我们能够在多项式的时间复杂度内验证一个答案是否正确，我们就把这类问题称为 NP 问题，其中 NP 表示不确定的多项式时间（non-deterministic polynomial time）。简单来说就是解决 NP 问题很难，但验证它却很容易。打个比方，数独是一个解决起来比较难的问题，但是如果我们往格子里随机填一些数字，然后验证它是否满足数独的规则就会比较容易。因此，这类问题也是科学家们最关心的问题。

多项式规约

既然 NP 问题都是比较难的问题，那么是否存在一个 NP 问题，使得所有 NP 问题可以通过多项式规约（polynomially reducible）得到它？这里的多项式规约指的是问题 A 的所有实例都能够在多项式的时间复杂度内转化为问题 B 的所有实例。规约后，如果问题依然是一个 NP 问题，我们就把它称作 NP-complete 问题；相反如果不是一个 NP 问题，我们称它为 NP-hard 问题。

举个例子，一元一次方程和一元二次方程的问题都是 NP 问题，因为我们可以选取一个 \(x\) 值，然后代入验证是否满足方程。我们发现，一元一次方程的问题可以规约成一元二次方程的问题，规约的过程很简单，只需要将 \(x\) 二次项系数改为0即可。而且一元二次方程有求根公式，所以对于一元一次方程而言，我们也可以代入到求根公式中得到方程的解。因此，我们可以说只要能解决一元二次方程，便可以解决一元一次方程，因为后者可以规约到前者。

P = NP ？

那么问题来了，规约过后的 NP 问题能否在多项式的复杂度内解决呢？换句话说，P 问题和 NP 问题是否等价。如果 P = NP 就意味着任何能够在多项式的复杂度验证的问题也能够在多项式的复杂度解决它，反之则不成立。下图表示了 P, NP, NP-complete 和 NP-hard 之间的关系。

1694747477690

问题的意义

那就要小伙伴要说了，这个问题太深奥了，跟我们这种普通人没有关系呀。正是这个超级难的问题，还没有人证明出来，才保证了我们普通人的正常生活，因为很多关于密码学的问题都是基于 P ≠ NP 来的，正是基于这种假设才使我们的各种加密算法暂时不能被轻易的破解。所以，一旦证明出 P = NP，那将可能会导致一些颠覆性的变化。

首先来说说它的好处，因为 NP 问题大多数都是不能够在多项式的复杂度内解决的，所以一旦 P = NP，我们就可以将任何一个 NP 问题转化为一个 P 问题。因此，一些现在看起来很难的问题都能够轻松的解决它，比如围棋有了终极解，生物领域中可以轻松破解遗传密码来任意操纵基因序列，很多数学猜想能够用计算机来演算推导，大量难题被解决等等，这些都是一些好的方面。

但是也会带来很多负面的影响，P 如果等于 NP 会导致所有加密算法彻底失效，你的银行卡，手机密码，社交账号变得不再安全，黑客能够轻松进入你的电脑，比特币，区块链这些近年来很火的概念将会成为无人问津的领域，这样的例子还有很多很多。