多项式时间复杂度的定义与P问题？

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

多项式关系的形式为O(nk)，k是常数，n是问题的输入大小。 例如，时间复杂度为O(nlog(n))和O(n^3)，两者都是多项式时间复杂度。 时间复杂度为 O(n^log(n))，O(2^n) 为指数时间复杂度，O(n!) 为阶乘时间复杂度。 像O(a^n)和O(n!)型时间复杂度一样，它是非多项式级别的，其复杂度往往是计算机无法容忍的。

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

由于算法时间复杂度的表达式O(nk)可以为O(nk+nk−1)，因此在表示O(nk)=O(nk+nk−1)时，保留指数最高项为时间复杂度 的表达式，不用删除低指数项就可以看到多项式多项式！ 当然，单项式也算作多项式。

注：图G的顶点数称为图G的阶。

2.P问题

《算法导论》中给出的定义：能够在多项式时间内解决的问题是P问题（，多项式问题）。

更具体地说：P问题是指可以在多项式时间内解决的问题，例如：时间复杂度为O(nlog(n))的快速排序和堆排序，O(n2)时间复杂度的冒泡排序和直接选择排序等算法都是P问题，都是多项式时间算法。 相反，时间复杂度为 O(nlogn) 和 O(2n) 的算法是指数时间算法。

3.NP问题

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

例如，环路是一个NP问题，因为验证一条道路是否经过每个顶点可以在多项式时间内完成，但找到环路需要穷举所有可能性，并且不能直接求解。

另一个例子是大合数的素因数分解。 没有给定的公式可以直接找出合数的两个素因数是什么。 然而，验证两个数是否是质因数可以在多项式时间内完成，因此它也是非线性的。 确定性多项式问题，也称为NP问题。

之所以需要定义NP问题，是因为NP问题通常只能找到多项式算法。 我们不会期望多项式级算法能够解决我们甚至无法验证多项式解的问题。

简单来说，存在多项式时间算法的一类问题称为P类问题； 而梵蒂冈塔问题、推销员旅行问题等尚未找到多项式时间算法的问题则称为NP问题。 问题。 同时，P型问题是NP问题的一个子集。 换句话说，如果你能在多项式时间内解决一个问题，你就必须能够在多项式时间内验证问题的解决方案。

3.1 NP与P的关系

目前人类未解决的问题是：是否所有NP问题都是P型问题，即P=NP？ 这是世界上七大最难的数学问题之一。 虽然这个问题还没有得到解决，但一个总的趋势和大的方向是，人们普遍认为P=NP并不成立。 也就是说，大多数人认为至少存在一个NP问题不能具有多项式级别复杂度的算法。

人们之所以如此坚信P≠NP，是因为在研究NP问题的过程中，发现了一类非常特殊的NP问题，称为NP完全问题（Non-），也称为NPC问题。 正是NPC问题的存在，才让人们相信P≠NP。

4.NPC问题4.1还原

为了解释NPC问题，我们首先引入一个概念——约简（有的资料称之为“约简”（））。

减量的概念：

约简的标准概念：如果我们能找到这样一个变化规则，任意程序A的输入都可以按照这个规则转化为程序B的输入，使得两个程序的输出相同，那么我们说问题A可以化简为问题B，即问题A可以用问题B的解来解决，或者换句话说，问题A可以“变成”问题B。例如：一个变量的线性方程可以是“简化”为一个变量的二次方程。

还原特性：

约简有一个重要的性质：约简是传递的。 如果问题A可以简化为问题B，问题B可以简化为问题C，那么问题A必须简化为问题C。

减少的意思：

“问题A可以简化为问题B”有一个重要的直观含义：B的时间复杂度高于或等于A的时间复杂度。换句话说，问题A并不比问题B更难。

减量要求：

我们所说的“可约化”是指可以在“多项式时间”（-time）内约化，即对输入进行变换的方法可以在多项式时间内完成。 只有在多项式时间内完成的缩减过程才有意义。

4.2NPC问题

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问题还原到它即可。 后来电路变成了NPC问题，TSP问题（旅行商问题）也变成了NPC问题。 还有很多NPC问题已经被证明是NPC问题。 如果对任意NPC问题找到一个多项式算法，则所有NP问题都可以得到完美解决。 所以，正是因为NPC问题的存在，P=NP才变得难以置信。 P=NP问题还有很多有趣的地方等待大家进一步探索。 攀登信息学的顶峰是我们这一代人的终极目标。 我们现在要做的至少是不要混淆概念。

5.NPH问题

NPH问题（NP-hard ，英文NP-hard ），满足NPC问题定义的第二项但不一定满足第一项（即NP-Hard问题比NPC问题范围更广） ，但不一定是NP问题）。

NP-Hard 问题也很难找到具有多项式时间复杂度的算法，但它并不包含在我们的研究范围内，因为它不一定是 NP 问题。 即使针对 NPC 问题找到了多项式级算法，也可能找不到针对 NP-Hard 问题的多项式级算法。 事实上，由于NP-Hard放宽了约束，它可能比所有NPC问题具有更高的时间复杂度，从而更难解决。

参考

[1]

[2] 多项式时间算法。

[3]NP（非、非确定性多项式）。

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

[5]图论中的P、NP、NPC和NP-hard问题详解。