在了解以上各类问题时，需要清楚几个概念：多项式、时间复杂度…

形如 P n ( x ) = a ( n ) x n + a ( n − 1 ) x ( n − 1 ) + … + a ( 1 ) x + a ( 0 ) Pn(x)=a(n)x^n+a(n-1)x^(n-1)+…+a(1)x+a(0) Pn(x)=a(n)xn+a(n−1)x(n−1)+…+a(1)x+a(0)的函数，叫做多项式函数

时间复杂度是一个函数,它定性描述了该算法的运行时间，探讨的是当输入值接近无穷时，算法所需工作量的变化快慢程度。 需注意，时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当程序所处理的问题规模扩大后，程序需要的时间长度对应增长得有多快。也就是说，对于某一个程序，其处理某一个特定数据的效率不能衡量该程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。

不管数据有多大，程序处理所花的时间始终是那么多的，我们就说这个程序很好，具有O(1)的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，比如找n个数中的最大值这个程序的时间复杂度就是O(n)，为线性级复杂度；而像冒泡排序、插入排序等，数据扩大2倍，时间变慢4倍的，时间复杂度是 O ( n 2 ) O(n^2) O(n2)，为平方级复杂度。还有一些穷举类的算法，所需时间长度成几何阶数上涨，这就是 O ( a n ) ) O(a^n)) O(an))的指数级复杂度，甚至 O ( n ! ) O(n!) O(n!)的阶乘级复杂度。 前面的几类复杂度被分为两种级别，其中后者的复杂度无论如何都远远大于前者。像 O ( 1 ) ) , O ( l n ( n ) ) , O ( n a ) O(1)),O(ln(n)),O(n^a) O(1)),O(ln(n)),O(na)等，我们把它叫做多项式级复杂度，因为它的规模n出现在底数的位置；另一种像是 O ( a n ) 和 O ( n ! ) O(a^n)和O(n!) O(an)和O(n!)等，它是非多项式级的复杂度，其复杂度计算机往往不能承受。当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，往往会超时，除非是数据规模非常小。

什么是非确定性问题呢？有些计算问题是确定性的，比如加减乘除之类，你只要按照公式推导，按部就班一步步来，就可以得到结果。但是，有些问题是无法按部就班直接地计算出来。比如，找大质数的问题。有没有一个公式，你一套公式，就可以一步步推算出来，下一个质数应该是多少呢？这样的公式是没有的。再比如，大的合数分解质因数的问题，有没有一个公式，把合数代进去，就直接可以算出，它的因子各自是多少？也没有这样的公式。这种问题的答案，是无法直接计算得到的，只能通过间接的“猜算”来得到结果。这也就是非确定性问题。而这些问题的通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法，假如可以在多项式时间内算出来，就叫做多项式非确定性问题。

如果对于某个确定的常数 k k k,存在一个能在 O ( n k ) O(n^k) O(nk)时间内求解出某具体问题的算法，就说该具体问题是一个多项式时间可解问题。

是一个判定问题，答案只有是或否。例如，存在某具体问题，我们猜想该问题有一个可行解 x x x，如果对于某个确定的常数 k k k，存在一个能在 O ( n k ) O(n^k) O(nk)时间内验证 x x x是否是该具体问题可行解的算法，就说该具体问题是一个多项式时间可被验证的问题。

你会经常看到网上出现“这怎么做，这不是NP问题吗”、“这个只有搜了，这已经被证明是NP问题了”之类的话。你要知道，大多数人此时所说的NP问题其实都是指的NPC问题。他们没有搞清楚NP问题和NPC问题的概念。NP问题并不是那种“只有搜才行”的问题，NPC问题才是。好，行了，基本上这个误解已经被澄清了。下面的内容都是在讲什么是P问题，什么是NP问题，什么是NPC问题，你如果不是很感兴趣就可以不看了。接下来你可以看到，把NP问题当成是 NPC问题是一个多大的错误。

《算法导论》给出的定义：

例如：时间复杂度为 O ( n l o g ( n ) ) O(nlog(n)) O(nlog(n))的快速排序和堆排序，以及冒泡排序和直接选择排序算法都是P问题，也就是多项式时间算法。当然，如果一个问题是P问题，那么毫无疑问我们可以在多项式时间内验证它。

然后扯个题外话，为什么我们要研究这个？因为计算机处理的输入常常不是那么几十个几千个那么一点点，想象一下，当计算机处理的数据达到100万个的时候，时间复杂度为 o ( n 2 ) o(n^2) o(n2)和 o ( e n ) o(e^n) o(en)的算法，所需的运行次数简直是天壤之别， o ( e n ) o(e^n) o(en)指数级的可能运行好几天都没法完成任务，所以我们才要研究一个问题是否存在多项式时间算法。而我们也只在乎一个问题是否存在多项式算法，因为一个时间复杂度比多项式算法还要复杂的算法研究起来是没有任何实际意义的。

NP问题（(Non-deterministic Polynomial Problem，非确定性多项式问题），可以在多项式时间内被验证的问题。或者说，可以在非确定性多项式时间内被解决的问题。所谓非确定性指的是问题只能通过验证猜测来解，而不能直接求解。 所谓的非确定性是指，可用一定数量的运算去解决多项式时间内可解决的问题。

之所以要定义NP问题，是因为通常只有NP问题才可能找到多项式的算法。我们不会指望一个连多项式地验证一个解都不行的问题存在一个解决它的多项式级的算法。相信读者很快明白，信息学中的号称最困难的问题——“NP问题”，实际上是在探讨NP问题与P类问题的关系。

很显然，所有的P类问题都是NP问题。也就是说，能多项式地解决一个问题，必然能多项式地验证一个问题的解——既然正解都出来了，验证任意给定的解也只需要比较一下就可以了。关键是，人们想知道，是否所有的NP问题都是P类问题。我们可以再用集合的观点来说明。如果把所有P类问题归为一个集合P中，把所有 NP问题划进另一个集合NP中，那么，显然有P属于NP。现在，所有对NP问题的研究都集中在一个问题上，即究竟是否有P=NP？通常所谓的“NP问题”，其实就一句话：证明或推翻P=NP。

NP问题一直都是信息学的巅峰。巅峰，意即很引人注目但难以解决。在信息学研究中，这是一个耗费了很多时间和精力也没有解决的终极问题，好比物理学中的大统一和数学中的歌德巴赫猜想等。

目前为止这个问题还“啃不动”。但是，一个总的趋势、一个大方向是有的。人们普遍认为，P=NP不成立，也就是说，多数人相信，存在至少一个不可能有多项式级复杂度的算法的NP问题。人们如此坚信P≠NP是有原因的，就是在研究NP问题的过程中找出了一类非常特殊的NP问题叫做NP-完全问题，也即所谓的 NPC问题。C是英文单词“完全”的第一个字母。正是NPC问题的存在，使人们相信P≠NP。下文将花大量篇幅介绍NPC问题，你从中可以体会到NPC问题使P=NP变得多么不可思议。

约化的标准概念：如果能找到这样一个变化法则，对任意一个程序A的输入，都能按这个法则变换成程序B的输入，使两程序的输出相同，那么我们说，问题A可约化为问题B，即可以用问题B的解法解决问题A，或者说，问题A可以“变成”问题B。 可以理解为问题B的解一定就是问题A的解，因此解决A不会难于解决B。由此可知问题B的时间复杂度一定大于等于问题A。如：一元一次方程可以“归约”为一元二次方程。这个规则即是：两个方程的对应项系数不变，一元二次方程的二次项系数为0。 性质：传递性。如果问题A可约化为问题B，问题B可约化为问题C，则问题A一定可约化为问题C。 要求： 我们所说的“可约化”指的是可“多项式时间地”约化(Polynomial-time Reducible)，即变换输入的方法是能在多项式的时间里完成的。约化的过程只有用多项式的时间完成才有意义。

好了，从约化的定义中我们看到，一个问题约化为另一个问题，时间复杂度增加了，问题的应用范围也增大了。通过对某些问题的不断约化，我们能够不断寻找复杂度更高，但应用范围更广的算法来代替复杂度虽然低，但只能用于很小的一类问题的算法。再回想前面讲的P和NP问题，联想起约化的传递性，自然地，我们会想问，如果不断地约化上去，不断找到能“通吃”若干小NP问题的一个稍复杂的大NP问题，那么最后是否有可能找到一个时间复杂度最高，并且能“通吃”所有的 NP问题的这样一个超级NP问题？答案居然是肯定的。也就是说，存在这样一个NP问题，所有的NP问题都可以约化成它。换句话说，只要解决了这个问题，那么所有的NP问题都解决了。这种问题的存在难以置信，并且更加不可思议的是，这种问题不只一个，它有很多个，它是一类问题。这一类问题就是传说中的NPC 问题，也就是NP-完全问题。NPC问题的出现使整个NP问题的研究得到了飞跃式的发展。我们有理由相信，NPC问题是最复杂的问题。再次回到全文开头，我们可以看到，人们想表达一个问题不存在多项式的高效算法时应该说它“属于NPC问题”。

NPC问题是指满足下面两个条件的问题： （1）它是一个NP问题； （2）所有的NP问题都可以用多项式时间约化到它。

既然所有的NP问题都能约化成NPC问题，那么只要任意一个NPC问题找到了一个多项式的算法，那么所有的NP问题都能用这个算法解决了，NP也就等于P 了。因此，给NPC找一个多项式算法太不可思议了。因此，前文才说，“正是NPC问题的存在，使人们相信P≠NP”。我们可以就此直观地理解，NPC问题目前没有多项式的有效算法，只能用指数级甚至阶乘级复杂度的搜索。

目前，NPC问题还没有找到一个多项式时间算法，因此我们就此可直观地理解，NPC问题目前没有多项式时间复杂度的有效算法，只能用指数级甚至阶乘级复杂度的搜索。

证明npc问题的思路就是： 先证明它至少是一个NP问题，再证明其中一个已知的NPC问题能约化到它。

逻辑电路问题是第一个NPC问题。逻辑电路问题指的是这样一个问题：给定一个逻辑电路，问是否存在一种输入使输出为True。逻辑电路问题属于NPC问题。这是有严格证明的。它显然属于NP问题，并且可以直接证明所有的NP问题都可以约化到它（不要以为NP问题有无穷多个将给证明造成不可逾越的困难）。证明过程相当复杂，其大概意思是说任意一个NP问题的输入和输出都可以转换成逻辑电路的输入和输出（想想计算机内部也不过是一些0和1的运算），因此对于一个NP问题来说，问题转化成了求出满足结果为True的一个输入（即一个可行解）。有了第一个NPC问题后，一大堆NPC问题就出现了，因为再证明一个新的NPC问题只需要将一个已知的NPC问题约化到它就行了。后来，Hamilton回路成了NPC问题，TSP问题（旅行商问题）也成了NPC问题。现在被证明是NPC问题的还有很多，任何一个NPC问题找到了多项式算法的话所有的NP问题都可以完美解决了。因此说，正是因为NPC问题的存在，P=NP变得难以置信。

NPH问题（NP难问题，英文NP-hard问题），其满足NPC问题定义的第二条但不一定要满足第一条（就是说，NP-Hard问题要比 NPC问题的范围广，但不一定是NP问题）。 NP-Hard问题同样难以找到多项式时间复杂度的算法，但它不列入我们的研究范围，因为它不一定是NP问题。即使NPC问题发现了多项式级的算法，NP-Hard问题有可能仍然无法得到多项式级的算法。事实上，由于NP-Hard放宽了限定条件，它将有可能比所有的NPC问题的时间复杂度更高从而更难以解决。

说明：

P Problem: 对于任意的输入规模 n，问题都可以在多项式时间内得到解决； NP(Non-deterministic Polynomial) Problem: 不能在多项式时间内解决或不确定能不能在多项式时间内解决，但能在多项式时间验证的问题 NPC(Non-deterministic Polynomial Complete) Problem: 满足两个条件:

NP-hard Problem: 满足NPC问题的第 2 条，但不一定要满足第 1 条。（NP-Hard问题要比 NPC问题的范围广）所以，TSP等NPC问题也是NP-Hard问题。

旅行商问题，即TSP问题（Traveling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

参考：https://blog.csdn.net/qq_37006625/article/details/86380825