为了弄清楚上面的概念以及对他们有个基本的了解，所以总结出这篇blog。

1.多项式时间复杂度

定义：解决问题需要的时间与问题的规模之间是多项式关系。

多项式关系形如 O ( n k ) O(n^k) O(nk)，k 为某个常数，n 是问题的输入规模。例如，时间复杂度为 O ( n l o g ( n ) ) O(nlog(n)) O(nlog(n))、 O ( n 3 ) O(n^3) O(n3) 都是多项式时间复杂度。时间复杂度为 O ( n l o g ( n ) ) O(n^log(n)) O(nlog(n))、 O ( 2 n ) O(2^n) O(2n) 是指数时间复杂度，O(n!) 是阶乘时间复杂度。像 O(a^n) 和 O(n!) 型的时间复杂度，它是非多项式级的，其复杂度计算机往往不能承受。

为什么多项式时间复杂度的定义形式是 O ( n k ) O(n^k) O(nk)呢，它的多项式的多项性体现在哪呢？

因为算法时间复杂度的表达式 O ( n k ) O(n^k) O(nk) 可以为 O ( n k + n k − 1 ) O(n^k+n^{k-1}) O(nk+nk−1)，在表示时 O ( n k ) = O ( n k + n k − 1 ) O(n^k)=O(n^k+n^{k-1}) O(nk)=O(nk+nk−1)，取指数最高项保留作为时间复杂度的表达式，未删除低指数项就可以看出多项式的多项性了吧！当然，单项式也算作多项式。

注：图 G 的顶点个数称为图 G 的阶（Order）。

2.P 问题

《算法导论》给出的定义：在多项式时间内可解的问题为 P 问题（Polynomial Problem，多项式问题）。

更为具体的是：P 问题指可以在多项式时间内求解的问题，例如：时间复杂度为 O(nlog(n)) 的快速排序和堆排序， O ( n 2 ) O(n^2) O(n2) 的冒泡排序和直接选择排序算法都是P问题，也就是多项式时间算法。相反，时间复杂度为 O ( n l o g n ) O(n^{logn}) O(nlogn)、 O ( 2 n ) O(2^n) O(2n) 的算法是指数时间算法。

3.NP 问题

定义：NP问题（(Non-deterministic Polynomial Problem，非确定性多项式问题），指问题只能通过验证给定的猜测是否正确来求解。所谓多项式指的是验证猜测可在多项式时间内完成，所谓非确定性指的是问题只能通过验证猜测来解，而不能直接求解。

如Hamilton回路是NP问题，因为验证一条路是否恰好经过了每一个顶点可在多项式时间内完成，但是找出一个Hamilton回路却要穷举所有可能性，不能直接求解。

又如大合数的质因数分解，没有给定的公式可直接求出一个合数的两个质因数是什么，但是验证两个数是否是质因数却可在多项式时间完成，所以它也是非确定性多项式问题，即NP问题。

之所以要定义NP问题，是因为通常只有NP问题才可能找到多项式的算法。我们不会指望一个连多项式地验证一个解都不行的问题存在一个解决它的多项式级的算法。

简单的说，存在多项式时间的算法的一类问题，称之为P类问题；而像梵塔问题，推销员旅行问题等问题，至今没有找到多项式时间算法解的一类问题，称之为NP问题。同时，P类问题是NP问题的一个子集。也就是说，能多项式时间地解决一个问题，必然能多项式时间地验证一个问题的解。

3.1 NP 与 P 的关系

目前，人类还未解决的问题是：是否所有的NP问题都是P类问题，即P=NP?。这就是注明的世界七大数学难题之首。虽然这个问题尚未解决，但是，一个总的趋势和大方向是人们普遍认为，P=NP不成立，也就是说，多数人相信，存在至少一个不可能有多项式级复杂度的算法的NP问题。

人们如此坚信P≠NP是有原因的，就是在研究NP问题的过程中找出了一类非常特殊的NP问题叫做NP-完全问题（Non-deterministic Polynomial Complete Problem），也即所谓的 NPC问题。正是NPC问题的存在，使人们相信P≠NP。

4.NPC 问题

4.1 约化

为了说明 NPC 问题，我们先引入一个概念——约化（Reducibility，有的资料上叫“归约”（Reduction）) 。

约化的概念：

约化的标准概念：如果能找到这样一个变化法则，对任意一个程序 A 的输入，都能按这个法则变换成程序B的输入，使两程序的输出相同，那么我们说，问题 A 可约化为问题 B，即可以用问题 B 的解法解决问题 A，或者说，问题 A 可以“变成”问题 B。 如：一元一次方程可以“归约”为一元二次方程。

约化的性质：

约化具有一项重要的性质：约化具有传递性。如果问题 A 可约化为问题B，问题 B 可约化为问题 C，则问题 A 一定可约化为问题 C。

约化的意义：

问题 A 可约化为问题 B 有一个重要的直观意义：B 的时间复杂度高于或者等于 A 的时间复杂度。也就是说，问题 A 不比问题 B 难。

约化的要求：

我们所说的“可约化”指的是可“多项式时间地”约化（Polynomial-time Reducible)，即变换输入的方法是能在多项式的时间里完成的。约化的过程只有用多项式的时间完成才有意义。

4.2 NPC 问题

NPC 问题是指满足下面两个条件的问题：

（1）它是一个 NP 问题；

（2）所有的 NP 问题都可以用多项式时间约化到它。

所以显然NP完全问题具有如下性质：它可以在多项式时间内求解，当且仅当所有的其他的NP完全问题也可以在多项式时间内求解。这样一来,只要我们找到一个NPC问题的多项式解，所有的NP问题都可以多项式时间内约化成这个NPC问题，再用多项式时间解决，这样NP就等于P了。

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

大多数人的观点对于 P类问题，NP类问题，NPC之间的关系可用下图表示（此图正确性有待验证）：

4.3 第一个 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 变得难以置信。P=NP 问题还有许多有趣的东西，有待大家自己进一步的挖掘。攀登这个信息学的巅峰是我们这一代的终极目标。现在我们需要做的，至少是不要把概念弄混淆了。

5.NPH 问题

NPH问题（NP难问题，英文NP-hard问题），其满足NPC问题定义的第二条但不一定要满足第一条（就是说，NP-Hard问题要比 NPC问题的范围广，但不一定是NP问题）。

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

参考文献

[1] 0001算法笔记——NP完全理论

[2] 多项式时间算法

[3] NP(Non-Deterministic Polynomial, 非确定多项式) .

[4] 什么是P问题、NP问题和NPC问题.

[5] 图论中P、NP、NPC和NP难问题详解.