NP 完全性

概念

P 类问题就是多项式时间内可以解决的问题。更为确切的说，这些问题可以在时间 $O(n^k)$ 内解决, 其中 $k$ 为某一常量， $n$ 是此问题输入的规模。常见的问题很多都是 P 类问题，比如

NP 问题是多项式时间内不可解的，但是可以在多项式时间内被验证。即给定一个解，我们可以在多项式时间内验证它的正确性。如：

一个NPC问题需要同时满足两个条件：① 该问题是NP问题；② NP里所有问题可以在多项式时间内归约到该问题。

满足 NPC问题的条件 ② : NP里所有问题可以在多项式时间内归约到该问题

定义抽象问题 Q 为在问题实例集合 I 和问题解集合 S 上的一个二元关系。

例如，最短路问题的一个实例是由一个图和两个顶点所组成的三元组，其解为图中的顶点序列，序列可能为空(两个顶点间不存在通路)。最短路问题本身就是一个关系，它把图的每个实例和两个顶点与图中联系这两个顶点的最短路径联系在了一起，因为最短路径不一定是唯一的，因此，一个给定的问题实例可能有多个解。

为了简单起见， NP 完全性问题主要考察的是判定问题，即那些解为是或否的问题。于是，我们可以把抽象的判定问题看做是从实例集 I 映射到解集 $\{0, 1\}$ 上的一个函数

例如路径存在问题，如果 $i=(G, u, v, k)$ 是判定问题 PATH 的一个实例，那么若从 $u$ 到 $v$ 的最短路径的长度至多为 $k$ 条边，则 PATH(i)=1 (是), 否则 PATH(i)=0 (否)

许多抽象问题并不是判定问题，而是最优化问题，在这些问题中，某些量必须被最大化或者最小化。