P
多项式时间内能求解的问题
多项式时间的算法的形式化定义是,对于规模为n的输入,在最坏情况下的运行时间是O(n的k次幂),其中k为某一确定常数。
相对应的,有伪多项式时间算法,典型的0-1背包问题算法复杂度为O(nW),其运行时间与输入的规模相关,是伪多项式的。
NP
多项式时间内能验证的问题
验证方法
NPC
是多项式时间内能验证的问题,而且是一个最难的问题。两个特点1.NP,2.NP-Hard
关系
证明一个问题是NPC
这些问题时如何通过归约的技巧证明是NPC的,往下看。
多项式归约
目的
我们希望在多项式时间内解决一个判断问题。如果这个问题还是NP的,那么它就是一个NPC问题。
方法
-
简单恒等
就是说问题A和问题B在时间上是等价的,这里有一个独立集和点覆盖问题
的简单恒等方式的归约过程。 -
将特例归约到一般化的例子
某一特定问题(A)的输入为该问题的实例。假设有另一不同的判定问题B,已知在多项式时间解决它的算法。我们将A的任何实例 α 转化成B的实例,而且转化过程是多项式时间的,且两个实例的解相同,也就是说需要证明双向归约。
这里是例子:点覆盖到集合覆盖的归约