算法设计学习笔记（八）NP与计算的难解性_独立集问题和点覆盖问题规约

---

前言

本文是对于算法设计的学习笔记，如有错误，请不吝赐教。

---

NP完全问题：NP完全性意味着：在计算上实际是难的，虽然我们不能证明它。

一、多项式时间归约

Y多项式时间可归约到X（或者X至少像Y一样的难）

1.1 第一个规约：独立集与顶点覆盖

在这里我们回顾独立集的定义：在图G=（V,E）中，如果顶点集合V中的任意两点间都没有边，那么称V是独立的。
独立集问题就是在图G中寻找一个最大的独立集。
为了方便研究，我们将问题修改为：
给定图G和数K，问G中是否包含大小至少为k的独立集。

顶点覆盖（没有已知的有效算法）：给定图G=（V,E），顶点S属于V，如果每一条边e至有一个定点在S中，我们称S是一个顶点覆盖。
顶点覆盖问题：给定图G和数k，G中是否包含大小至少为k的顶点覆盖。

补充证明：假设S是一个独立集，考虑任意一边（u，v），可知u，v必有一个在V-S中，所以可知V-S是一个顶点覆盖。

由此我们可以得到一个这两个问题的归约。

补充证明：假设有一个解顶点覆盖的黑盒子，那么通过问黑盒子G是否有大小至多为n-k的顶点覆盖，那么就能确定G是否有大小为k的独立集。

反之亦然

由此我们知道了以上两个问题的相对困难水平。

1.2 归约到更一般的情况：从顶点覆盖到集合覆盖

独立集和顶点覆盖是两种不同类型的问题。
独立集可以看做包装问题：装入尽可能多的顶点，要从服从一些限制条件（边）
顶点覆盖可以看做一个覆盖问题：用尽可能少的顶点覆盖图中所有的边。

顶点覆盖是特殊的覆盖问题，而集合覆盖是更为一般的覆盖问题。在集合覆盖中，试图用一组较小的组合覆盖一个任意的对象集合。
覆盖问题的具体描述如下：

具体我们可以这样做:
我们对每个顶点v，设Sv是图中所有与i关联的边，把sv加入到集合覆盖的实例中。
我们可知如果U能被s1，s2，，，sn中的至多k个覆盖，当且仅当G有大小至多为k的定点覆盖。（如果s1,s2,sl是l<=k的覆盖U的集合，那么G中的每一条边都关联到i1，i2。。。il顶点，所以其中i1，i2，i3是G中大小为l<=k的顶点覆盖。反之亦然）

而对于独立集而言，独立集的自然推广是关于任意集合的包装问题。
具体的集合包装问题定义如下：

二、使用零件的归约：可满足性问题

2.1SAT和3-SAT

举例如下：

可满足问题（SAT）：

如果所有的字句都包含3个项，那么这个问题被称作三元可满足性（3-SAT）

2.2 将3-SAT归约到独立集

具体证明如下：
两个项冲突：一个项等于变量xi，另一个等于他的否定xi！

归约具体过程见p327

2.3 归约的传递性

三、有效证书和np的定义

3.1 问题与算法

我们可以认为一个计算问题的输入被编码为有穷的二进制串s。串s的长度记作|s|，把判定问题X等同于对它的答案为yes的串组成的集合。判定问题的算法那A接受输入串s并返回yes或者no，这个返回这记作As，如果对于所有的串s,As=yes，当且仅当s属于X，那么就称A解问题X。
而如果存在多项式P，使得对于每个输入s，算法A都有在至多OP步内终止，那么称A有多项式运行时间。

3.2 有效证书

有效验证程序B：

我们可以人为有效验证程序并不打算亲自去判断输入S是否属于X，而愿意去有效的评估所提交的s属于X的证据t。

3.3 NP：一个问题类

定义Np是所有存在有效验证程序的问题的集合。

补充：

我们目前相信p！=Np

补充：p问题是在多项式时间内可解的问题。
Np问题：问题只能通过验证给定的猜测是否正确来求解。所谓多项式：验证猜测可在多项式时间内完成。且问题只能通过验证猜测来解，而不能直接求解。

四、NP完全问题

Np中最难的问题：
1）X属于NP
2）对于所有的Y属于np，由Y<=px 即np中的每个问题都能够归约到X
我们称这样的X是NP完全问题。

4.1 电路可满足性：第一个NP完全问题

我们定义电路K是一个带标号的有向无圈图。
K中的源节点的标号为常数0,1或者不同的变量名，这被看做是电路的输入
其他节点都标有布尔运算
有唯一一个不带离开边的节点，他表示输出即电路计算的结果。

如下如图所示：

电路可满足性问题如下：
给定一个电路，需要确定是否存在对输入的赋值使得输出值为1

具体证明如下：

例如：

4.2 证明更多的问题是NP完全的

对于上述结论的证明，我们可以通过归约电路可满足性来进行。

如果Sat中的只有一个项t的子句，我们可以考虑用
方式来完成，其中z1=z2=0

4.3 证明新NP完全问题的通用策略

后者的归约可能会多次请求黑盒子（Karp归约，Cook归约）

五、排序问题

5.1 巡回售货员问题

问题：有一位巡回售货员，他必须访问n个城市，分别记作v1，v2。。。vn，售货员从他居住的城市v1出发，想找一条旅行路线，即访问所有的城市最后回到家的顺序，他的目标是整个旅行路线的距离尽可能的小。
在实际应用中，旅行者问题运用在许多场合（规划人工机械臂有效动作，io请求，n个模块的执行顺序等）

5.2 哈密尔顿问题

给定一个有向图G=V，E，如果G中的圈C恰好经过每个顶点一次，则称圈C是一个哈密顿图。即它构成一条经过所有顶点的，没有重复的路线。

5.3 证明哈密尔顿问题是NP完全的

5.4 证明巡回售货员是NP完全的

通过将哈密尔顿归约到巡回售货员得到上述结论。

5.5 推广:哈密顿路径问题

哈密顿圈的一个变种是不需要回到出发点。
我们同样也可以证明哈密顿路径是NP完全的。（同样采用3-SAT的归约或者是哈密顿圈归约到哈密顿路径上）

六、划分问题

6.1 三维匹配问题

三维匹配问题可以看做是二部图匹配问题的难解形式。

满足上述条件的有序三元组集合叫做一个完美的三维匹配。
（三维匹配同时是集合覆盖和集合包装的特殊情况）

6.2 证明三维匹配是NP完全的

我们可以容易证明三维匹配是NP的。（可以在多项式时间内验证解）
（设计一些零件表示对每个变量的真值赋值的独立选择，然后添加一些零件表示字句强加的约束。）

具体证明见P342

七、图着色

7.1 图着色问题

给定一个无向图G，我们对G中的每一个节点分配一种颜色，使得如果（u,v）是一条边，则分配给u，v不同的颜色，目标是使用很少的几种颜色就做到这一点。
如果G有一个k-着色，那么称它是k-可着色的图。
相关应用：

7.2 图着色问题的计算复杂性

而往上的三着色等问题会更加复杂。

7.3 证明三着色问题是NP完全的

考虑字句

具体证明见P345

7.4 四色问题的猜想

四色猜想是对于区域数的归纳。

八、数值问题

使用非常大的整数表示问题的编码。

8.1 子集和问题

这类问题的基本问题是子集和问题。
表述如下：

当数w较大时，该问题就变得非常复杂。

8.2 证明子集和问题是NP完全的

我们将三维匹配问题归约到子集和问题。（组合选择问题）
具体证明见P348

8.3 推广：某些调度问题的难度

子集和的难度可以用来给出某些调度问题的难度，包括一些不明显含有数值加法的调度问题在内。
比如带开发时间和截止时间的调度问题：

证明见P349

8.3 说明：有多项式界限数值的子集和

比如分支聚合问题不是np完全的。

九、co-NP以及NP的不对称性

9.1 好的特性

十、难问题的部分分类

10.1 包装问题

10.2 覆盖问题

10.3 划分问题

10.4 排序问题

10.5 数值问题

10.6 约束满足问题