作者joywilliamjo (joywilliamjoy)
看板Grad-ProbAsk
標題[理工] 109 清大 計算機科學 演算法 第九題
時間Mon Nov 29 23:22:24 2021
https://i.imgur.com/9q4cbPz.jpg
這題有辦法用題目給的2 partition去證出 3 partition也是NPC嗎？
我知道兩個reduce到subset sum
但用subset sum去證的話會不會不夠嚴謹？
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.136.161.51 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1638199346.A.78B.html
1F：推 foogty: 我的想法是這樣，構建一個新集合S'為S集合再添加一個新的11/30 07:24
2F：→ foogty: 數字k,當S'存在3 partition 則 S存在 2 partition, S中存11/30 07:24
3F：→ foogty: 在2 partition 也可以推到S'中存在3 partition ,不曉得這11/30 07:24
4F：→ foogty: 樣是不是對的11/30 07:24
5F：推 VF84: 樓上的想法很接近了，我幫他補充細節11/30 07:39
6F：→ VF84: 給定一個 multiset S，其元素總和為 2T，則在 S 中添加11/30 07:40
7F：→ VF84: T，就可以用 3-partition 去判斷是否存在 2-partition11/30 07:40
9F：推 foogty: 感謝補充11/30 07:48
10F：→ joywilliamjo: 感謝，懂了11/30 09:53
11F：→ mathtsai: CLRS NPC reduce那章節應該有教吧11/30 18:42
有教怎麼全部reduce到subset sum,沒有單純的3partition到2partition
※ 編輯: joywilliamjo (101.136.64.176 臺灣), 12/01/2021 15:51:38