作者OforU (待)
看板Grad-ProbAsk
标题[理工] NP-Complete NPC
时间Mon Dec 24 21:48:21 2018
(更新：刚刚贴错题目)
证明NPC:
Given an integer k,
a universe U and a family S = {S1, S2, . . . , Sm}
whose union equals U, where each Si is a subset of U,
find out whether there is a sub-family C ⊆ S of at most size k
whose union is the universe U.
请各位大大给个指点
我目前完全没想法
想不到要Reduction到什麽东西QQ
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 223.136.91.77
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1545659304.A.0C0.html
1F：推 eggy1018: HP reduce 到 HC12/24 22:06
啊啊 大大抱歉 刚刚贴错题目了Orz
※ 编辑: OforU (223.136.91.77), 12/24/2018 22:14:04
2F：推 eggy1018: 加一点p使得p->u,v->p各连到p，形成一instance G’，若12/24 22:12
3F：→ eggy1018: 能在此G’中找到HC，因为v->p & p->u连，所以若G’中有H12/24 22:12
4F：→ eggy1018: C，则原图G中一定有由u开始v结束的HP12/24 22:12
5F：→ eggy1018: 以上有错还请告知12/24 22:12
6F：推 eggy1018: 第一句改成*加一点p使得p->u,v->p，没有各连到p12/24 22:14
感谢大大前面的回答
7F：→ eggy1018: 我觉得是sunset-sum，可以reduce到3-CNF12/24 22:25
大大可否再说详细
要怎麽看成subset sum problem呢?
※ 编辑: OforU (223.136.91.77), 12/24/2018 22:32:36
8F：推 FRAXIS: 用 Vertex cover reduce 到这问题 12/25 06:23
9F：推 a66862439: 用subset sum 相对於size去做subset sum为k的问题 不知 12/25 14:16
10F：→ a66862439: 道这样可不可解 12/25 14:16
11F：推 booowei1203: vertex cover -> set cover 12/14 10:35