算法设计与分析笔记之NP完备性理论

一. P、NP、NPC

三类问题都会涉及到多项式时间算法，我们先解决什么是多项式时间算法。
多项式时间的算法的形式化定义是，对于规模为n的输入，在最坏情况下的运行时间是 $O(n^{k})$ ，其中k为某一确定常数。相对应的，有伪多项式时间算法，典型的0-1背包问题算法复杂度为 $O(nW)$ ，其运行时间与输入的规模相关，是伪多项式的。

1. P(Polynomial-time)：在多项式时间内可以求解的问题

如以下表格中的都是P类问题。

P类问题

2. NP(Nondeterministic Polynomial-time)：在多项式时间内可以被证明（验证）的问题

NP问题能找到多项式时间的验证算法。
什么叫验证？例如，在哈密尔顿圈问题中，Z为图中点的一个序列。如果我们能设计一个多项式时间的判定算法，判定这个序列是否是一个哈密尔顿圈，那么称这个问题能在多项式时间内验证，序列Z是这个问题的一个证书（Certificate）。
如何证明一个问题是NP问题？

找到该问题的一个证书；
阐述用此证书验证的过程。

注意：不用证明这个问题没有多项式时间求解算法，因为P类问题是NP问题的子集，只需有证书验证过程即可。

3. NPC(NP Completeness)：NP中最难的问题

非形式化定义，如果一个NP问题和其他任何NP问题一样“不易解决”（归约），那么我们认为这一问题是NPC类问题或称之为NP完全问题。
形式化定义，问题X是NP完全的，如果：

$X∈NP$ ；
对每一个 $X'∈NP$ ，有 $X'≤_{p}X$ .

NP问题可在多项式时间归约到NPC问题。特殊地，如果一个问题满足2，而不一定满足1，则称它是NP难度（NP-Hard）的。
反过来，要证明一个问题Y是NP完全的。可以采用如下步骤：

证明问题Y是一个NP问题；
选择一个NPC问题X；
证明X ≤p Y（注意方向）。

常接触到的NPC问题

4. P、NP、NPC的关系

P⊆NP，P是否是NP的真子集，这是7个千玺数学难题之一。目前，大部分计算机科学家相信P≠NP。
NPC问题能在多项式时间内解决，当且仅当P=NP。如果任何一个NPC问题能在多项式时间内得到解决，那么，NP中的每个问题都能在多项式时间内解决，即P=NP。等价地，如果存在某一NP问题不是多项式时间可求解的，则所有NPC问题都不是多项式时间可求解的。
各NPC问题在多项式时间等价。
被大多数计算机科学家接受的关系

P、NP、NPC以及NPH间的关系

写了这么多，我还是看不懂。就这样理解叭，P类问题是可以在多项式时间求解的问题，但大部分问题都是不能的。因此我们想用一些数据去验证它是不是这个问题的解，如果能在多项式时间验证出来，那么这个问题就是NP问题。其中，NP里最难的问题我们叫它NPC问题，但有些问题跟NPC问题差不多难，然而它又不是NP问题，就只好说它是NP难度的，也就是NP难问题（NP-Hard）。

二. 多项式归约

1. 多项式归约的含义

目的：我们希望在多项式时间内解决一个判断问题。
准备：某一特定问题（A）的输入为该问题的实例。例如，寻找路径（PATH）问题的实例可以是图G、G中特定的点u和v以及一个特定的整数k（是否存在u到v长度为k的路径）。
假设有另一不同的判定问题B，已知在多项式时间解决它的算法。我们将A的任何实例 α 转化成B的具有以下特征的某个实例 β：

转化操作需要多项式时间
两个实例的解相同，即 α 的解是“是”，当且仅当β的解是“是”。（这个当且仅当暗示你证明归约是双向的）

这一过程就是多项式时间归约算法。它提供了一种在多项式时间内解决A的方法：

给定问题A的实例 α ，利用多项式时间归约算法，将它转化为问题B的一个实例 β ；
在实例 β 上，运行B的多项式时间判定算法；
将 β 的解作为 α 的解。

多项式时间归约算法还为我们提供了比较各种问题的难易程度的方法（或者说按难易程度将NP问题分类）。例如，X ≤p Y，那么问题X不会比问题Y难多于一个多项式时间的因子，也就是Y比X难。
如果X ≤p Y且Y ≤p X，则X ≡p Y
注意上述所说的所有解决算法都是指解决如何判定问题的算法，并不能真正求解。

2. 归约的三种基本策略

简单恒等
将特例归约到一般化例子
利用小技巧（想不出的小技巧）

参考资料：《算法导论》