作者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/m.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