在讨论算法时，人们常说这个问题的解决方法是p类问题，或者是NP的难题。 于是我特意找了这方面的资料，自己做了总结。 研究算法的大家应该知道。 如果我总结的哪里错了，请一起讨论~
在谈到p类问题之前，我先介绍两个概念：多项式、时间复杂度。 (知道这两个概念的人可以自动跳过这一部分)
1、多项式：axn-bxn-1+c
嗯……是这样的形状。 x的最高次是n的多项式.
诶，别讨厌我吵。 也许有人忘了什么是多项式了。 例如，第一次看到的朴素的人_
2、时间复杂度
众所周知，在计算机算法求解问题中，一种算法的执行效率往往用时间复杂度和空间复杂度来表示。 空间复杂度表示算法在计算过程中消耗的内存空间的大小，但这里不讨论。 时间复杂度表示运行该算法得到期望解所需的计算工作量，研究输入值无限接近时算法所需工作量变化的快慢。
举个例子，泡沫排序。
在计算机中，排序问题是最基础的，按大小和其他规则对输入进行排序有利于以后使用数据进行其他运算。 泡沫排序是其中的一种排序算法。 假设手里现在有n个无序的数，用泡沫排序对其进行排序的话，
首先比较第一个个数和第二个个数，如果是后者的前者，则调换他们的位置。 否则，不会改变
接着比较第二个和第三个，如果是后者的前者，调换他们的位置，否则不变
第n-1个和第n个个数比较结束，向下比较直到第1轮结束。 (此时最大的数量移动到了第n个个数的位置)
重复前三步，但只比较到第n-1个个数(将第二大的数移动到第n-1个个数位置) ) ) ) ) ) ) ) ) ) )。
对于不断增加的要素，每次重复上述步骤，直到没有需要比较的数字对为止。
举个例子，可以计算出5、4、3、2、1对其进行排序，首先将5与4进行比较，变为4、5、3、2、1，第一轮结束后为43215。 对此进行排序时，必须经过正好4、3、2、1=10次的比较。 当然，这是最复杂的情况。 也就是说，完全相反的顺序。 可以看出，关于n的个数，至多要经过1(n-1即(n^2-n )/2次的比较才能排序。 在该式中，n的最高次为2，但在n的情况下，可知一次对比较次数的影响较小，因此将该算法的时间复杂度比喻为o () ) n^2。 取其最高次，可以看出这是时间复杂度为多项式。
时间复杂度排名o(1) o(1 ) o ) lgn (o ) n^2) o(1 ) o (e ^ n ) ) a2，n表示输入的数据数量，o(1)是常数水平)
那么，介绍了上面的概念之后，就可以开始谈论什么是p类了。 以上例气泡排序为例，我们发现在排序这个大问题中，气泡排序法这样的时间复杂度可以找到多项式o(n^2)的算法来求解排序问题，所以我们说排序问题是一个具有多项式时间算法的问题。
所以我们，
P类问题:存在多项式时间算法问题。 (P:polynominal，多项式) ) ) ) ) ) ) ) ) ) )。
还有闲话，我们为什么要研究这个？ 计算机处理的输入往往不是几十个、几千个左右，请想象一下。 当计算机处理的数据达到100万个时，时间复杂度为o(n )和o(n ) n )的算法可能需要的执行次数与天壤之别，o(n ) n )指数函数无法执行好几天，因此多项式时间算法因为研究时间复杂度比多项式算法更复杂的算法没有任何意义。
那么，接下来介绍NP。 首先给出定义。
NP类问题：多项式时间内得到正确解的问题。 (NP : nondeterministicpolynominal，非确定多项式)
p型问题是NP问题的子集，由于存在多项式时间解法的问题，经常在多项式时间内验证他。
请注意定义。 这里是验证。 关于NP类问题，我用个人的俗话来理解，这个问题被称为非确定性，因为不知道多项式时间内是否存在算法，可以在多项式时间内进行验证，得到这个问题的正确答案。 举个例子，
知名NP类问题：旅行家销售问题(TSP )。 也就是说，有一个向n个城市出售商品的推销员，他必须找到包括n个城市全部在内的环路。 这个环路路径小于a。 我知道这个问题单纯用枚举法列举的话会有(n-1 )！ 种子不再是多项式时间的算法。 (注：阶乘算法比多项式复杂。 我该怎么办？ 我们可以猜。 假设我的人品好，猜了几次就猜了比长度a小的路径。 我画画，是的，我得到了比a小的路径循环，问题解决了，我很高兴。 但是，我不能每次都那么准确地推测。 我可能会猜出所有种类吗？ 所以，这是NP类的问题。 也就是说，我们可以在多项式时间内验证并给出问题的正确答案，但我们不知道那个问题是否存在多项式时间算法，每次都可以解决他(请注意这里不知道，不是不存在)。
所以这引起了这样的讨论
论的一个千年问题：是否 NP类问题=P类问题？即，是否所有能在多项式时间内验证得出正确解的问题，都是具有多项式时间算法的问题呢？
太让人震惊了，要是解决了这个问题，那岂不是所有的NP问题都可以通过计算机来解决？
圣战的结果是，有的存在，有的不存在。=_=
在这场圣战中，人们还发现了很多的东东，也就是我们接下来要介绍的NPC问题(啊喂，我不是游戏NPC)和NPH问题。
(PS :网络上经常有人说，这不是个NP问题吗，其实很多时候他们说的应该是NPC问题，而不是NP问题)
为了证明这个千古难题，科学家想出了很多办法。其中之一就是问题的约化。所谓问题约化就是，可以用问题B的算法来解决A ，我们就说问题A可以约化成问题B。举个例子，一元一次方程的求解，跟二元一次方程的求解，我们知道，只要能求解二元一次方程，那就可以用二元一次方程的解法来求解一元一次方程，只需要将一元一次方程加上y，并附加一个方程y=0就可以将一元一次方程变形为一个二元一次方程，然后用二元一次方程的解法来求解这个方程。注意，这里二元一次方程的解法会比一元一次的复杂。所以我们说，只需要找到解二元一次方程的规则性解法，那就能用这个规则性解法来求解一元一次方程。从这里也可以看出，约化是具有传递性的，如A约化到B，B约化到C，A就可以约化到C，同时不断约化下去，我们会发现一个很惊人的特性，就是他一定会存在一个最大的问题，而我们只需要解决了这个问题，那其下的所有问题也就解决啦！这就是我们所说的NPC问题的概念！！！
引到NP问题里就是，对于同一类的所有的NP类问题，若他们都可以在多项式时间内约化成最难的一个NP类问题，（我们直观的认为，被约化成的问题应具有比前一个问题更复杂的时间复杂度）当我们针对这个时间复杂度最高的超级NP问题要是能找到他的多项式时间算法的话，那就等于变向的证明了其下的所有问题都是存在多项式算法的，即NP=P！！！！给出NPC问题定义，
NPC问题:如果所有np问题都能在多项式时间内转化为他，则称该np问题为npc问题(NPC:NP complete又叫NP完全问题)
NPC问题是NP问题的子集。
当然，很多时候NPC问题是找不到一个多项式时间算法的，更多时候他是一个指数级的算法。
最后介绍下NPH问题。
NPH问题：我们又叫NP难问题，他不是一个NP问题，然后所有的NPC问题都可以在多项式时间内转化为他的话，我们就叫他NPH（hard）问题。
至此，介绍完了这四大问题，感觉自己像在写小说一样，越写越兴奋，哈哈，简直又臭又长~~