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

问题

1. SAT问题

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

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

2. 01整数规划

给定整数矩阵C和整数向量d,问是否存在01向量x使得\(Cx\geq d\).

注:似乎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当且仅当\(Ax\geq b\)。

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

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,使得\(|W\cap U_i|=1\)对每个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连权值为\(|S_j|\)的边,如果ui在Sj中,则ui和Sj之间连权值为0的边。

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

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

17. 三维匹配

给定一个集合\(U\subset T\times T\times T\),其中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的一个排列\(\pi\)),使得未完成任务的总惩罚不超过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. 最大割
给定图G,边权为整数 。求是否存在一个点集S,使得S向外的边的权值之和大于等于W.
求和划分规约到最大割:
假设有n个数{c1,c2,…,cn}.我们建立n个顶点的完全图G,其中i的点权为ci,边(i,j)的权值为ci*cj.
设c1+c2+…+cn=C.如果我们选取的点集S的点权之和为a,则这个割的割值就是a*(C-a)。这是一个关于a的二次函数,当a=C/2的时候取最大值。因此,{c1,c2,…,cn}可划分成和相等的两部分当且仅当有一个值等于\(C^2/4\)的割。

《Karp的21个NPC问题和部分证明》有2个想法

  1. 18 的证明有点不严谨,可能有反例,例如用 {1,2}, {2}, {2}, 就凑出来了一个 {3}. 必须没有重复的集合才行

发表评论

电子邮件地址不会被公开。 必填项已用*标注