P、NP、NPC问题以及归约方法总结

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的实例，而且转化过程是多项式时间的，且两个实例的解相同，也就是说需要证明双向归约。
  这里是例子：点覆盖到集合覆盖的归约