作者yushes920179 (樂冰)
看板Grad-ProbAsk
標題[理工] np complete reduction
時間Wed Aug 26 11:22:05 2020
一直有點無法理解reduce方向
https://i.imgur.com/YYXHZRD.jpg
這裡的(b)我的理解是這樣
https://i.imgur.com/kDwUCF6.jpg
我看題目都是從SAT 變到 要證的np complete
所以reduce方向這樣寫不知有沒有錯
再來是
https://i.imgur.com/RHt3ZvS.jpg
這裡的（2）我的理解是這樣
https://i.imgur.com/pE5arHY.jpg
這裡的<=p 的符號我理解是難度的大小比較
所以p2是NP hard 不能證明比它簡單的p1是NP hard
煩求各位救救小弟
-----
Sent from JPTT on my iPhone
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.138.41 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1598412127.A.746.html