[理工] 演算法 NP-complete

看板Grad-ProbAsk作者yorunohoshi (夜の星)時間9年前 (2016/11/23 14:49)推噓3(3推 0噓 2→)

留言5則, 3人參與討論串1/1

http://imgur.com/a/71WoR 大家好想請問這題的第二小題我的理解是：所有的NP問題都可以reduce成NP-complete的問題因此只要找到一個polynomial time的Algo可解NP-complete 則NP問題皆可在多項式時間解那第二小題錯的原因是因為有可能是某些NP(or NP-complete)問題在轉換時需要O(n^4)以上的時間嗎？這樣NP問題都可以在多項式時間內解，只是某些不一定被bound在O(n^3)？不知道這樣解釋對不對@@ 想請教大家想法謝謝~ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.77.11 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1479883791.A.1AA.html ※ 編輯: yorunohoshi (140.112.77.11), 11/23/2016 14:52:51

推

aa06697

11/23 17:28, , 1^F

11/23 17:28, 1^F

→

aa06697

11/23 17:28, , 2^F

11/23 17:28, 2^F

推

PTTleader

11/23 18:46, , 3^F

11/23 18:46, 3^F