Karp的21个NPC问题和部分证明

问题

1. SAT问题

问题P为若干个子句的逻辑与，每个子句是若干变量的逻辑或（P是合取范式/CNF），问是否存在一组输入，使得P为真。

根据对偶性，这一问题可以表述为：命题S是若干子句的逻辑或，每个子句是若干变量的逻辑与（S是析取范式/DNF），问S是否为恒真命题。

2. 01整数规划

给定整数矩阵C和整数向量d，问是否存在01向量x使得[latex]Cx\geq d[/latex].

注：似乎Karp原论文中此处把“大于等于”误为“等于”：

https://cs.stackexchange.com/questions/19716/0-1-integer-programming-and-karps-reduction

SAT问题（合取范式P）规约到01整数规划：

我们构造矩阵A和向量b，对于P的子句i（Pi是若干个变量的逻辑或）：

• 如果Pi中有变量xj，则A[i,j]=1
• 如果Pi中有变量not xj，则A[i,j]=-1
• 否则，A[i,j]=0
• bi = 1 – (Pi中出现的not xj形式的变量个数)

01向量x满足问题P当且仅当[latex]Ax\geq b[/latex]。

原理是：如果x不满足Pi，我们假设Pi是n个“xi”和m个“not xi”的并，可以想象，Pi中所有应当为True的变量在x中都为False，它们贡献的和为0，而所有应为False的变量在x中都为True，它们贡献的和为-m，所以总的和就是-m.其余所有情况下，Pi均满足，和都大于-m，也就是大于等于1-m.因此x满足Pi当且仅当[latex]A_i x\geq b_i[/latex]

3. 团问题

问图G中是否存在大小为k的团(完全子图)。

SAT问题（合取范式P）规约到团问题：

构造点集V为{<x, i> : 变量x出现在子句Pi中}

构造边集E为{ {<x, i>, <y,j>} : i,j不等且x不是not y }

假设SAT问题有解。我们按照点集V的构造法，让所有“变量x在Pi中为True”的<x,i>构成一个G中的点集R。显然，R中有每一个i（因为要求P的每一个子句为True），所以R中至少p个点。另一方面，R中不能有矛盾，即R中所有属于不同子句的点均按照规则“x不是not y”连边。我们取出R中属于不同子句的p个点，则它们构成一个大小为p的团。所以在团问题中检查是否存在大小为p的团，就可以解SAT。

另一方面，如果G中有大小为p的团，则这个团一定是在每个子句中包含一个变量，且变量之间无矛盾。我们在SAT中选取这些变量为True，即得到一组解。

4. 不相交集合

给定一组集合{Sn},问其中是否存在k个互不相交的集合。

团问题规约到不相交集合：

假设图G的点集是{1,2,…,n}.构造n个集合{S1,S2,…,Sn}，其中Si = { {i,j} : {i,j}是G中的边 }，其中{i,j}是无序集。注意到集合相交的唯一情况是形如Si和Sj中都包含{i,j}，这意味着i和j相邻。因此，i,j不相邻当且仅当Si和Sj不相交，所以G中大小为k的团等价于{Sn}中k个不相交集合。

5. 点覆盖

问是否能用不超过k个点覆盖图G中的所有边。

团问题规约到点覆盖：

假设图G有n个顶点。G中存在点数不少于k的团当且仅当G的补图中存在点数不少于k的独立集（就是这个团），当且仅当G的补图中存在点数不超过n-k的点覆盖（就是那个独立集的补集，如果它未覆盖一条边，说明这条边的两端都在独立集中，矛盾）。所以G中存在点数不少于k的团等价于G的补图中存在点数不超过n-k的点覆盖。

6. 集合覆盖

给定有限个有限集合{Sn}，问能否找出其中不超过k个集合，覆盖{Sn}之并中所有的元素。

点覆盖规约到集合覆盖：

集合i就是顶点i引出的边集。大小为k的点覆盖等价于这k个集合覆盖所有边集。

7. 反馈点集

给定有向图G，问是否存在大小不超过k的点集R，使得G中所有环都包含一个R中的点。

点覆盖规约到反馈点集：

把图G中的每条边(u,v)拆成一条去边<u,v>和一条回边<v,u>，这样形成的新图为H。

一方面，如果G中存在点数不超过k的点覆盖R，则R覆盖了H中的所有边，毋宁说H中的环。

另一方面，如果H中存在点数不超过k的反馈点集，可以看到，每个<u,v>和<v,u>构成一个环，所以这个反馈点集覆盖了G中的(u,v)，这就是G中点数不超过k的点覆盖。

所以G中存在点数不超过k的点覆盖当且仅当H中存在点数不超过k的反馈点集。

8. 反馈边集

给定有向图G，问是否存在大小不超过k的边集S，使得G中所有环都包含一条S中的边。

点覆盖规约到反馈边集：

把G中每个点u拆成入点u0和出点u1，对于G中的边(u,v)，作新图中两条边<u1,v0>和<v1,u0>，记新图为H。

一方面，对于G中的点覆盖R，我们在H中选取所有的<u0,u1>，其中u在R中。由于R覆盖了G中所有的边，那么H中的一个环必然包括R中的某个u，而我们选了<u0,u1>，就符合反馈边集的条件。

另一方面，G中每条边(u,v)在H中对应一个环(<u0,u1>,<u1,v0>,<v0,v1>,<v1,u0>)，如果H中存在一个反馈边集，它应当至少包括这四条边之一。在G中选取那个对应的入点，显然它在G中覆盖了(u,v).

所以G中存在一个大小为k的点覆盖当且仅当H中存在一个大小为k的反馈边集。

9. 有向哈密顿回路

给定有向图G，问是否存在一条恰经过所有点一次的回路。

证明待补充

10. 无向哈密顿回路

给定无向图G，问是否存在一条恰经过所有点一次的回路。

有向哈密顿回路规约到无向哈密顿回路：

把G中的每个点u拆成三个点u0,u1,u2.连无向边(u0,u1),(u1,u2)，对于G中的有向边<u,v>，连无向边(u2,v0).记新图为H。如果G中有有向哈密顿回路，那么按着走下来就是H中的无向哈密顿回路。如果H中有无向哈密顿回路，那么它每个点的类型一定是012012012……或者210210210……这就是说，它要么是正着走的G的有向哈密顿回路，要么是倒着走的G的有向哈密顿回路。

所以G中的有向哈密顿回路等价于H中的无向哈密顿回路。

11. 3-SAT问题

问是否存在一组输入满足所有的子句，每个子句是至多3个变量做逻辑或，每个变量形如x或者not x

SAT问题规约到3-SAT：

对于一个子句x1 or x2 or … or xm，我们新建一个变量y1，然后把它转化成以下的子句：

• x1 or x2 or y1
• x3 or x4 or … or xm or (not y1)
• (not x3) or y1
• (not x4) or y1
• …
• (not xm) or y1

可以证明它和原来的x1 or x2 or … or xm等价。

如此往复，直至把SAT问题变成若干个三元子句。

12. 染色数

给定一张图G，问是否可以做k染色。

3-SAT规约到染色问题：

假设3-SAT问题D的子句是D1,D2,…,Dr.不失一般性，假设D中的元素是u1,u2,…,um.

我们建一个图G，它的点集为：u1, u2, …, um, u1′, u2′, …, um’, D1, D2, …, Dr, v1, v2, …, vm. 其中ui’代表not ui，v1,…,vm是新加的点。

我们添加五类边：

1. 每个ui和ui’连边。
2. 如果i,j不等，连(vi,vj)
3. 如果i,j不等，连(vi,xj)和(vi,xj’)
4. 如果ui不在子句Df中，连(ui,Df)
5. 如果ui’ 在Df中，连(ui’, Df)

证明待补充

13. 团覆盖

给定图G，问G中是否存在不超过k个团，覆盖所有的顶点。

染色问题规约到团覆盖：

把i号团的顶点染成颜色i（或者取颜色为i的顶点为i号团），那么G中存在不超过k个团的覆盖当且仅当G的补图可以k染色。

14. 恰好覆盖

给定一组集合{Sn}，每个都是U={u1,…,ut}的子集，问是否存在若干个{Sn}中的集合，使得它们两两不交，而且覆盖U（全部并起来等于U）.

证明待补充

15. 击中集

给定一组集合{Un}，每个都是S={s1,…,sr}的子集，问是否存在一个S的子集W，使得[latex]|W\cap U_i|=1[/latex]对每个i成立。也就是W恰好“击中”每个Ui一次。

“恰好覆盖”规约到击中集：

我们把“恰好覆盖”问题中的元素u1,…,ut作为二分图的左边节点，集合S1,S2,…,Sm作为二分图的右边节点。ui在Sj中，就在它们之间连一条边。那么，恰好覆盖问题等于：选择右边的一些节点，把它们发出的所有边染红，使得左边每个点都恰巧连了一条红边。

另一方面，我们把击中集问题的元素s1,…,sr作为二分图的右边节点，集合U1,…,Un作为二分图的左边节点，如果si在Uj中，就在二者之间连边。那么击中集问题等于：选择右边的一些节点，把它们发出的所有边染红，使得左边每个点都恰巧连了一条红边。

所以击中集和恰好覆盖等价。

16. 斯坦纳树

给定图G和其中的一个顶点集R，问是否存在一个G的生成树T，使得T的边权值不超过k，且T包含R中所有顶点。要求所有边的权值都是整数。

“恰好覆盖”规约到斯坦纳树：

我们假设“恰好覆盖”问题的全体元素是{u1,u2,…,ut}，有若干个集合{Si}。现在构造图G：每个ui都是G中的一个点，每个Si也是G中的一个点，除此之外再加上一个点n0.

n0和所有的Sj连权值为[latex]|S_j|[/latex]的边，如果ui在Sj中，则ui和Sj之间连权值为0的边。

我们把{ui}排成一竖列放在最右边，{Si}排成一竖列放在中间，n0放在最左边。那么图G中一棵生成树的样子是：n0向中间一列的若干个Si连边，这些Si再引出边，覆盖右边一列的所有ui。其中，u0向中间Si一列连的边的权值是Si中的元素数，Si一列向ui一列的边不消耗权值。因此这棵生成树的权值就是选取的集合的元素个数之和。

显然，“恰好覆盖”当且仅当能选出若干个元素个数之和恰好为t的集合，覆盖所有的ui，也就是说，存在一个权值为t的斯坦纳树。因此二者等价。

17. 三维匹配

给定一个集合[latex]U\subset T\times T\times T[/latex]，其中T是一个n元集。问是否存在U的子集W，使得W中有n个元素，但是W中的任意两个元素的任意两个坐标都不相等。

证明待补充

18. 01背包

给定r件物品，重量为a1,a2,…,ar，问其中能否选出若干个，使得重量之和恰好为b.
“恰好覆盖”规约到01背包：

我们令元素ui的重量为2^i，每个集合的重量就是它包含的元素重量之和。那么恰好覆盖和选中的集合的重量在每个第i位上只有一个1等价。所以恰好覆盖等价于01背包。

19. 任务分配

有p个任务，i号任务的执行时间是Ti，期限是Di，完不成任务的惩罚是Pi。问是否存在一个执行任务的序列（也就是1,2,…,p的一个排列[latex]\pi[/latex]），使得未完成任务的总惩罚不超过k.

01背包规约到任务分配：

假设背包总容量为b。我们对于重量为ai的物品，构造任务i：它的耗时为ai，超时惩罚为ai，期限b。那么，背包能“恰好放满”就等价于能构造出一个“恰好用完时间”的任务，它的超时惩罚为(总耗时-b).于是01背包等价于任务分配。

20. 求和划分

给定一个整数集合C，问能否把C中的元素分成两部分，每一部分的和相等。

01背包规约到求和划分：
假设现有的元素为a1,a2,…,ar.

再构造两个元素：b+1, (a1+…+ar)+1-b.这r+2个元素的和为2(a1+…+ar+1).假设它能划分成和相等的两份，(a1+…+ar)+1-b所在的一份中，余下的元素肯定不包括b+1（否则就超了），所以一定是若干个ai加起来等于b。于是01背包等价于求和划分。

21. 最大割