NP 完全性问题介绍¶
1. P 与 NP¶
以前一直不知道所谓 P 与 NP 是什么意思，那么这里简单介绍一下，有时间复杂度这个概念，还是比较简单的。
假设我们有一个可以计算的机器，可以是理论上的图灵机，或者是现实的计算机什么的，进行一次运算的操作消耗单位时间。
有些算法的复杂度很低，比如排序，对 n 个数进行排序的时间复杂度，可以达到 \(O(n \log n)\)。有些算法的复杂度就很高了，比如说用 dfs 进行搜索，复杂度是 \(2^n\)。如果问题大小都是 100，一个只需要最多 10000 次，一个则需要 \(2^{100}\) 次，是天差地别了。
\(O(n^k)\) 内解决问题的算法称为可以在多项式时间内解决的算法。我们认为这个问题可以被“较为容易”地解决。
如果一个问题，可以在多项式时间内求解出其具体问题，就说该具体问题是多项式时间可解的。即解决该问题算法的复杂度可以达到 \(O(n^k)\) 。那么这就是 P 类问题。比如说，排序算法就是 P 类问题，初学者学习的冒泡排序，也只需要 \(O(n^2)\) 的时间复杂度。
对有些问题，我们不知道他能否在多项式时间内解决，但是，给一个这个问题的答案，我们可以“较为容易”地验证这个答案是否确实是这个问题的解；就是说，存在一个多项式时间的验证算法。这类问题的统称为 NP 类问题（nondeterministic polynomial time）。
举书本上的哈密顿回路问题：无向图 \(G(V,E)\) 中的一条哈密顿回路是通过 V 中每一个顶点一次的简单回路。问题是：对一个给定的无向图，判断其是否存在一条哈密顿回路。
考虑朴素的求解算法是，全排列 V 中的所有点，一个个判断其是否满足回路的条件。如果有 n 个点，复杂度是 \(O(n!)\)，比 \(O(2^n)\) 还夸张。这个算法不是多项式时间的。
但是，要验证一个回路是否是哈密顿回路，则很简单：验证回路是否是 V 的一个排列，再验证回路中的每条边是否出现在图中。如果有 n 个点，那验证算法应该 \(O(n)\) 就可以完成了。
我们目前还不知道哈密顿回路是否是 P 类问题，但是可以肯定，根据上述的分析，它是一个 NP 类问题。
很显然，\(P \subseteq NP\)。求解过程本身就需要验证解是否是问题的解。如果验证算法不是多项式时间，则求解算法不是多项式时间，与 P 的定义矛盾。
目前还未知道是否有 \(P=NP\)。从经验来说，验证问题的解往往比求解问题本身简单的多，所以更多人持否定态度。
2. 问题归约¶
我们想求解一个问题 \(Q\)，可以先去求解另一个问题 \(Q'\)，如果两个问题的解是相同的（可以一一对应的），并且进行问题转化的算法只需多项式时间，那么可以说 \(Q\) 可以被归约成另一个问题 \(Q'\)，可以写作 \(Q \leq_p Q'\)
下面举一些问题归约的例子。
布尔可满足性问题（SAT）是经典的问题。给定一个逻辑表达式，判断是否存在一组变量赋值使表达式为真。
3-SAT 可满足性问题则是特殊情况，给定的逻辑表达式必须是合取范式（CNF）：逻辑表达式是所有子句的与，所有子句是 3 个文字的或。如：\((a \lor b \lor c) \land (\neg a \lor \neg b \lor \neg c)\)。
我知道任意的逻辑表达式都可以转化成 3-CNF，说明转化的算法是多项式时间的就可以了。这样就可以完成了一个问题的归约。
3-SAT 问题又可以归约成团问题（CLIQUE）：团是图 G 的一个顶点子集，每一对顶点之间都有 G 中的一条边连接。团问题是判断图 G 中是否有规模为 k 的团。（规模是团的顶点数）。具体过程可以见《算法导论》。
团问题可以归约成顶点覆盖（VERTEX_COVER）问题，顶点覆盖问题又可以归约成哈密顿回路（HAM-CYCLE）问题，哈密顿回路问题归约成旅行商（TSP）问题。
3. NP-complete¶
\(Q \leq_p Q'\)，问题归约说明了什么呢？可以说明两个问题几乎是一样难。
有这样一类问题 \(Q\)，它非常的难。它满足了这样的定义，对 np 中的任意一个问题 \(Q'\)，都可以归约成 \(Q\)，即 \(\forall Q' \in \text{np}, Q' \leq_p Q\)。这样的问题 \(Q\) 称为 NP-hard 问题。
如果问题 \(Q\) 自己又是一个 NP 类的问题，那么 \(Q\) 是一个 NP-complete 问题。
根据定义，我们可以得出下面结论：若任意一个 NP-complete 问题都可在多项式时间内求解，则 \(P=NP\)（证明：前提可以导致 \(NP \subseteq P\)）。反之，若存在一个 NP 中的问题不是多项式时间可求解，则所有 NP-complete 问题都不可在多项式时间内求解。
第一个被证明了 NP-complete 的问题就是布尔可满足性问题。Cook-Levin 定理。
然后，在 2 中举例了问题归约的例子：
这里的问题都是 NP 问题，根据定义，就都是 NP-complete 问题了（\(\leq_p\) 有传递性）。比如说，我们一开始提到的哈密顿回路问题，就是一个 NP-complete 问题。
目前，我们还未找到任何算法能够在多项式时间内解决哪怕一个 NP-complete 问题（总是要指数时间）。可是，我们也没能证明这些问题就是不可能属于 P。
那只好折中，碰到一个新问题，或者想办法想一个高效算法，或者想办法将它归约成一个 NP-complete 问题，说明它很难。
读了《算法》和《算法导论》写的笔记，以前一直没有看懂，今天看了，感觉不是很难，但还是记录一下吧，算是了解了新知识。《算法导论》中给出了非常严格的形式化定义，可以看看。