[理工] 109 清大 計算機科學 演算法 第九題

[joywilliamjo (joywilliamjoy)]

https://i.imgur.com/9q4cbPz.jpg
這題有辦法用題目給的2 partition去證出 3 partition也是NPC嗎？
我知道兩個reduce到subset sum
但用subset sum去證的話會不會不夠嚴謹？

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.136.161.51 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1638199346.A.78B.html
推 foogty: 我的想法是這樣，構建一個新集合S'為S集合再添加一個新的
→ foogty: 數字k,當S'存在3 partition 則 S存在 2 partition, S中存
→ foogty: 在2 partition 也可以推到S'中存在3 partition ,不曉得這
→ foogty: 樣是不是對的
推 VF84: 樓上的想法很接近了，我幫他補充細節
→ VF84: 給定一個 multiset S，其元素總和為 2T，則在 S 中添加
→ VF84: T，就可以用 3-partition 去判斷是否存在 2-partition
推 VF84: https://imgur.com/a/d2lrwtG.jpg
推 foogty: 感謝補充
→ joywilliamjo: 感謝，懂了
→ mathtsai: CLRS NPC reduce那章節應該有教吧
有教怎麼全部reduce到subset sum,沒有單純的3partition到2partition
※ 編輯: joywilliamjo (101.136.64.176 臺灣), 12/01/2021 15:51:38