算法(12)- NP完全性

P

L是{0, 1}* 的子集, 如果对任意的输入串x, 算法都能在多项式时间内判定(decide)x是否属于L, 则我们说算法能判定L, 这个语言L是P.
P = {L是{0, 1}※ 的子集, 存在着一个算法A, 可以在多项式时间内判定L};

NP

能够被多项式时间内算法A验证(verify)的语言L是NP问题. 也就是说, 给定了输入串x和一个猜测解y, 能够用某算法A在多项式时间内给出是1或者0, 1代表x∈L, 0代表x∉L. 这个语言L就是属于NP问题(Non Polynomial Deterministic Problem)

形式化定义:
一个语言L ∈ NP 当且仅当:
存在有两个输入的多项式时间算法A和常数c，使得
L = {x∈{0, 1}* : 存在一个证书(一个可满足解)y，其长度 |y| = O(|x|c)， 并使得A(x, y) = 1}.

L has a polynomial-time verifier, an algorithm V with the property that x ∈ L if and only if V accepts (x, y) for some y.

比如哈密顿回路问题: Ham-Cycle = {<G>: G is a HamGraph with a Ham cycle}

若某人给定了一个图G和一个环(也许是A-B-E-C-D-A), 声称该环为哈密顿回路, 我们可以很容易地设计一个简单的算法: "直接验证环上的点是否是包含了所有的图上的点, 以及这个环上的边是否确实在图中都存在."
这个算法将判定这样的有(G和环)的二输入是否是满足L = "图拥有哈密顿回路".

也就是说, 对L来说, 存在一个两输入的多项式时间算法A(x, y), 能够验证某特定输入(x, y)是属于L的.

NPC

NPC是NP中最难的语言, 如果任意一个NP完全问题(NPC问题)能够在多项式时间内得到解决, 那么NP中每一个问题都存在一个多项式解, 实现P = NP

证明某种语言L是NP完全语言的方法

(1)先验证L∈NP; //对一个串x, 存在一个多项式级别长度的解y, 能用一个多项式级别时间复杂度的算法A来verify ;

• Thus, we can verify CIRCUIT-SAT in polynomial time, and CIRCUIT-SAT ∈ NP. (CLRS)
  (2)规约: 把L'能够用多项式时间内的f映射到L, 说明L'<=L(L比已知的NPC还难), 加上已知L'是NP, 那么L必然是NP完全的;

几个重要的NPC问题的逻辑链

• CircuitSAT-->SAT-->3-CNF-SAT-->Clique-->VertexCover-->HamCycle-->TSP(旅行商问题)

1. CircuitSAT to SAT

布尔公式是可满足的
(1)SAT ∈ NP:
给定证书时多项式时间内可验证: 给定一个布尔公式x, 给定一个一个证书输入y, 比如y={1, 1, 1}, 然后按照布尔公式的数学运算规则, 那么我们就能在多项式时间内求解出来, 从而看到是否这个(x, y)能够得到1, 如果能得到, 那么其就是被满足了. 无论其最后是否被满足, 我们都能在多项式时间内验证出来.
(2)CircuitSAT能在多项式时间内规约为SAT问题
只要把电路中的x1, x2, x3每一个输入都用一个布尔变元表达, 然后每一个逻辑门都用一个布尔公式来对应, 那么就能在多项式时间内把CircuitSAT问题转化为SAT问题. 因此, CircuitSAT < SAT. SAT比已知为NPC的问题还难, 因此SAT也是NPC.

2. SAT to 3-CNF-SAT

合取范式形式的布尔公式的可满足性问题是NP完全的.
(1) 3-CNF-SAT ∈ NP:
给定证书时多项式时间内可验证: 类似SAT问题, 给定一个合取范式, 我们给定一个证书输入y, 然后按照数学运算规则, 那么我们能在多项式时间内得知整个合取范式的最后值是否为1.
(2) SAT能在多项式时间内规约为3-CNF-SAT:
通过如下步骤, 每个布尔公式都能成功地被转化为合取范式.
a. 画二叉语法分析树, 从而写出改写出一个合取范式(每个子句都是被满足才能整个式子成立), 但是此时子句里面还没有都变成析取;
b. 用真值表, 把表中所有子句最后能取0的项都拼出来, 就构成了一个析取范式AVBVC... (记得我们本来应该取的是表中子句最后值为1的情况, 这为接下去取反留了伏笔)
c. 用德摩根律取反析取范式, 从而得到CNF
d. 添加p, q的正反形式, 从而在每个子句凑够三个变元;

可以看到, 所有的SAT都能在多项式时间内(每一步有确定有限大小的步骤, 而不是n^n这样)的操作完成转化为3-CNF. 因此SAT<3-CNF-SAT, 从而3-CNF-SAT是NPC的.

3. Clique团问题

寻找图中规模最大的图案的最优化问题.
其等价的判定问题是CLIQUE = {<G, k>: G是一个包含规模为k的团}
证明团问题是NPC:
(1) Clique∈NP:
对于一个给定的图G=(V, E), 如果给定某顶点集V'作为G的一个证书, 那么我们可以检查任意一对顶点u, v∈V', 通过检查边(u, v)是否属于E(记得团的要求是该顶点集两两之间都得有边), 就可以在多项式时间内确定V'是否是一个团. C(n, 2) = O(n^2), 这是n的多项式时间.
(2) 把3-CNF-SAT规约到Clique:
通过如下步骤
给定一个含有k个子句的实例, 假定其是可满足的, 我们总是可以构造一个包含3k个顶点的图, 其中最大团是包含k个顶点. 构造方法: 不在同一个三元组, 且不是自己的非的结点之间连线.
那么我们知道一共会有k个分组, 每个分组之间不能相连, 且这个式子是可满足的, 因此每个分组必须出一个1, 只要把这个取1的元素和其他每个组取1的元素连接起来, 就是最大团. 而且最大团会有k个结点最后.
这个过程中只需要按照构造方法连线即可, 时间复杂度是O(C<n, 2>) = O(n^2)

4. Vertex Cover顶点覆盖问题

描述: 在一个给定的图中, 找出具有最小规模的顶点覆盖. 可以把这个最优化问题描述为一个判定问题, 即一个图是否具有一个给定规模k的顶点覆盖.
证明:
(1) VC∈NP:
(2) 把Clique规约到VC:
任意一个给定的Clique图G(V, E), 设其的最大团是V', 我们可以取其补图(原来有边变成没边, 没边变成有边), 即可获得V-V'为一个顶点覆盖.

这是因为取任意的一条边(u, v)自E', 那么在G中, u, v点原本是不相连的, 那么u或者v至少有一个是不属于最大团V'中的, 即u或者v至少有一个是属于V-V'的. 注意到(u, v)是我们任意取自E'的, 从而可知在G的补图里面, 任意的一条边上, 都有至少一个点是属于V-V'的, 那么V-V'就是一个顶点覆盖!!!

5. 哈密顿回路

无向图G中的哈密顿回路是指能通过V中每个顶点的简单回路.
哈密顿回路问题: 图G中是否有一条哈密顿回路(过所有点的简单回路).
证明很复杂, 我们只要知道Ham-Cycle问题是一个NPC即可.

6. 旅行商问题

描述: 售货员希望进行一次巡回旅行, 走一个哈密顿回路, 最后回到除法的城市, 从城市i到城市j的旅行费用为一个整数c(i, j), 旅行所需费的总费用是旅行经过的各边的费用之和, 而售货员希望使整个旅行费用最低. (最优化问题)
判定形式语言是: 图G中存在一个最大花费为k的旅行回路.
这是一个NPC.
证明:
(1) TSP∈NP:
给定一个图G, 限定最大花费为k, 那么给定一个证书y(y在这里是一个路线, 一个顶点的序列), 我们将可以检查: a, 该序列y包含且只包含了所有V中顶点一次. b, 该序列上的相邻顶点两两之间在图上是否有边 c,对序列y上的边的费用进行求和, 看是否在k之内. 这个过程是一个多项式时间内的算法, T = O(V).
(2) 把哈密顿回路问题归约到TSP:
对每一个哈密顿回路的一个实例G(V, E), 我们都可以构造这样一个TSP的图G'(V, E'), E' = {(i, j), 只要i!=j, i, j∈V};
c(i, j) = 0, if (i, j)∈E (E这里是哈密顿回路的边集合)
c(i, j) = 1, if (i, j) = 1 if (i, j)∉E.

然后求解TSP图G'上的限定最大花费为0的旅行路线.
显然这个构造的时间复杂度是O(V^2), 是多项式时间内的算法.