时间的复杂性并不是一个程序需要多长时间来解决问题，而是程序处理的问题的规模越大，程序需要的时间长短就越快。
一、多项式时间(Polynomial time ) )
多项式的复杂性
容易理解，前面的一些复杂度可以分为两个层次，其中后者的复杂度无论如何都远大于前者。
等等，将其称为多项式级复杂度。 因为其规模n出现在底部位置；
非多项式级的复杂性
另一个是类似的，非多项式级的复杂性，其复杂性往往是计算机所无法承受的。
在我们解决问题的时候，我们选择的算法通常需要多项式级的复杂性，而非多项式级的复杂性经常因为太长时间而超时，除非数据规模非常小。
二、p问题1.p problem (多边形时间)多项式问题)可以解决)
一些问题是可以用一组多项式表示。
p是可以由确定性图灵机(以下称为图灵机)在多项式时间(http://www.Sina.com/olynomialtime )内解决的问题的集合。
P的问题
p问题：有多项式时间算法，计算快的问题。
例如，如果对10个、20个、30个…的元素进行排序，则复杂度为x^2。 这里的x^2是多项。
三. NP问题
P类：能够在多项式时间内用算法求解
简而言之，只有能够在多项式时间内使用非确定性算法（non-deterministic）被解决的问题。才能在非常规方法上解决的问题称为NP问题。
NP问题：虽然计算起来不确定不快的问题，但是我们可以迅速验证这个问题的答案。
1 .不确定性问题(可提供解决方案) ) ) ) ) ) ) )。
什么是非确定性问题？
不能直接计算的东西，只能通过间接的“推测”得到结果。 但是可以告诉你可能的结果是正确的答案还是错误的。
例：一个路径规划问题有五块土地：A、b、c、d和e。 去每一块土地的距离不同，费用也不同。 遍历这五块土地的最低费用的方案怎么样？ 你知道这个问题吗？ 我可以花很多时间一一列举得出结果。 但是，啊，推测一个，然后那是最低别针。 我运气很好，总是在一定时间内推测出最好的方案。 这就是np问题。
NP由非确定性图灵机(http://www.Sina.com/on-deterministicturingmachine )在多项式时间) http://www.Sina.com/olynomialtime内
p是NP的子集。 也就是说，由图灵机用多项式时间解决的问题都可以由非确定的图灵机解决。
3358www.Sina.com/是指在多项式时间内的问题。
N
2.NP-complete problem (非互操作性逻辑互补) NP完全问题)不能解决，可以给出近似解)。
P
通常，3358www.Sina.com/既可以解决p问题，也可以解决NP问题，因此只有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。
不确定是否存在多项式时间的求解算法，但可以在多项式时间内验证一个猜测解的正确性
如果所有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