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