[理工] NP-Complete NPC (更新題目)

看板Grad-ProbAsk作者 (待)時間7年前 (2018/12/24 21:48), 7年前編輯推噓5(5推 0噓 5→)
留言10則, 3人參與, 7年前最新討論串1/1
(更新：剛剛貼錯題目) 證明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://www.ptt.cc/bbs/Grad-ProbAsk/M.1545659304.A.0C0.html
推
12/24 22:06, 7年前 , 1F
HP reduce 到 HC
12/24 22:06, 1F
啊啊 大大抱歉 剛剛貼錯題目了Orz ※ 編輯: OforU (223.136.91.77), 12/24/2018 22:14:04
推
12/24 22:12, 7年前 , 2F
加一點p使得p->u,v->p各連到p，形成一instance G’，若
12/24 22:12, 2F
→
12/24 22:12, 7年前 , 3F
能在此G’中找到HC，因為v->p & p->u連，所以若G’中有H
12/24 22:12, 3F
→
12/24 22:12, 7年前 , 4F
C，則原圖G中一定有由u開始v結束的HP
12/24 22:12, 4F
→
12/24 22:12, 7年前 , 5F
以上有錯還請告知
12/24 22:12, 5F
推
12/24 22:14, 7年前 , 6F
第一句改成*加一點p使得p->u,v->p，沒有各連到p
12/24 22:14, 6F
感謝大大前面的回答
→
12/24 22:25, 7年前 , 7F
我覺得是sunset-sum，可以reduce到3-CNF
12/24 22:25, 7F
大大可否再說詳細 要怎麼看成subset sum problem呢? ※ 編輯: OforU (223.136.91.77), 12/24/2018 22:32:36
推
12/25 06:23, 7年前 , 8F
用 Vertex cover reduce 到這問題
12/25 06:23, 8F
推
12/25 14:16, 7年前 , 9F
用subset sum 相對於size去做subset sum為k的問題 不知
12/25 14:16, 9F
→
12/25 14:16, 7年前 , 10F
道這樣可不可解
12/25 14:16, 10F
‣ 更多 OforU 的文章
文章代碼(AID): #1S8EEe30 (Grad-ProbAsk)