[理工] np complete reduction
一直有點無法理解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://www.ptt.cc/bbs/Grad-ProbAsk/M.1598412127.A.746.html