[理工] np complete reduction

作者: yushes920179 (樂冰)   2020-08-26 11:22:05
一直有點無法理解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
煩求各位救救小弟

Links booklink

Contact Us: admin [ a t ] ucptt.com