本文主要是介绍P problem、NP problem、NP-complete problem、NP-hard problem是什么，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当程序所处理的问题规模扩大后，程序需要的时间长度对应增长得有多快。
一、多项式时间（Polynomial time）
多项式复杂度
容易看出，前面的几类复杂度被分为两种级别，其中后者的复杂度无论如何都远远大于前者。
像
等，我们把它叫做多项式级复杂度，因为它的规模n出现在底数的位置；
非多项式级的复杂度
另一种像是
等，它是非多项式级的复杂度，其复杂度计算机往往不能承受。
当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，往往会超时，除非是数据规模非常小。
二、P问题
1. P problem（Polynomial-time）多项式问题（能解决）
说的是某些问题可以用一组多项式来表示。
P是一类可以通过确定性图灵机（以下简称 图灵机）在多项式时间(Polynomial time)内解决的问题集合。
P类:能够在多项式时间内用算法求解的问题
P问题：有多项式时间算法，算得很快的问题。
比如说，给10个、20个、30个… 元素排序，复杂度是 x^2 ，这里的x^2 就是一个多项。
三、NP问题
能够在多项式时间内使用非确定性算法（non-deterministic）被解决的问题。
简单来说就是，必须以非常规方法才能在多项式时间内解决的问题，就叫做NP问题。
NP问题：算起来不确定快不快的问题，但是我们可以快速验证这个问题的解。
1. NP problem（Nondeterministic polynomial-time）不确定性问题（能给出解决方案）
什么是非确定性问题呢？
无法直接计算得到的，只能通过间接的“猜算”来得到结果。但可以告诉你，某个可能的结果是正确的答案还是错误的。
例：一个路径规划问题，有5个地:A,B,C,D,E,一个地去另外一个地距离不一样，花费也不一样，问遍历完这5个地最低花销的方案是怎么样。这个问题你能知道，我花多点时间一个一个枚举可以得出结果的，但是呢，我猜一个，然后那个就是最低花销的，我运气特别好，总能在一定时间内猜到最佳方案，这就是np问题。
NP是一类可以通过非确定性图灵机( Non-deterministic Turing Machine)在多项式时间(Polynomial time)内解决的决策问题集合。
P是NP的子集，也就是说任何可以被图灵机在多项式时间内解决的问题都可以被非确定性的图灵机解决。
NP类:指不确定是否存在多项式时间的求解算法，但可以在多项式时间内验证一个猜测解的正确性的问题。
已有指数时间算法的判定问题,包括P类.
2. NP-complete problem（Non-deterministic Polynomial complete problem）NP完全问题（无法解决，可以给出近似解）
只能通过非确定性算法，在多项式时间内解决的问题，叫做NP完全问题。
一般来说，非常规方法既可以解决P问题，也可以解决NP问题，所以，只有用非常规方法才能解决的问题，才能叫做NP完全问题。
这个问题是由多个np问题抽象而成，他具有多个np问题的基本性质，因此只要这个np-complete问题解决了，与他关联的np-complete问题也就能解决。要成为np-complete问题，第一步，他是np问题；第二步，其他所有np问题都能约化（抽象）成他。
如果一个决策问题 L 是 NP-complete的，那么L具备以下两个性质：
1) L 是 NP（给定一个解决NP-complete的方案(solution)，可以很快验证是否可行，但不存在已知高效的方案 。）
2) NP里的任何问题可以在多项式时间内转为 L。
NPC类:是NP的一个子集,且其中每一个问题均能由NP中的任何问题在多项式时间内转化成.
如果所有NP问题可在多项式时间内归约成某个NP问题（归约，意思是解决了后者也就相应的解决了前者），则该NP问题称为NP完全问题。
NPC包含了NP中最难的问题。
所谓问题约化就是，可以用问题B的算法来解决A ，我们就说问题A可以约化成问题B。举个例子：一元一次方程的求解，跟二元一次方程的求解，我们知道，只要能求解二元一次方程，那就可以用二元一次方程的解法来求解一元一次方程，只需要将一元一次方程加上y，并附加一个方程y=0就可以将一元一次方程变形为一个二元一次方程，然后用二元一次方程的解法来求解这个方程。注意，这里二元一次方程的解法会比一元一次的复杂。所以我们说，只需要找到解二元一次方程的规则性解法，那就能用这个规则性解法来求解一元一次方程。从这里也可以看出，约化是具有传递性的，如A约化到B，B约化到C，A就可以约化到C，同时不断约化下去，我们会发现一个很惊人的特性，就是他一定会存在一个最大的问题，而我们只需要解决了这个问题，那其下的所有问题也就解决啦！这就是我们所说的NPC问题的概念！！！
3. NP-Hard problem（Non-deterministic Polynomial hard problem(NPH)）NP难问题，非多项式问题（无法解决，可以给出近似解）
如果说np-complete还是在多项式解决一个问题的范畴，np-hard问题会涉及到非多项式的问题。
NP-Hard问题是这样一种问题，它满足NPC问题定义的第二条但不一定要满足第一条（就是说，NP-Hard问题要比 NPC问题的范围广，NP-Hard问题没有限定属于NP），即所有的NP问题都能约化到它，但是它不一定是一个NP问题。
而NP-Hard只需要具备NP-complete的第二个性质，因此NP-complete是NP-Hard的子集。
若问题A不属于NP类,已知某一NPC问题可在多项式时间内转化为问题A,则称A为NPH.
NPH：如果所有NP问题可在多项式时间内转化（归约，意思是解决了后者也就相应的解决了前者）成某个问题，则该问题称为NP难问题。
三、这四者的关系如下图（假设P!=NP）：
https://www.cnblogs.com/sancyun/p/4250360.html
https://blog.csdn.net/wxdsdtc831/article/details/7942435
https://blog.csdn.net/sinat_21591675/article/details/86521190
https://blog.csdn.net/liusisi_/article/details/107160947
https://blog.csdn.net/weixin_39278265/article/details/115060817
这篇关于P problem、NP problem、NP-complete problem、NP-hard problem是什么的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
