[理工] 演算法 NP-complete

[yorunohoshi (夜の星)]

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: 個人想法跟你一樣 多項式時間可解未必都一樣大 n 跟 n^10
→ aa06697: 0 差蠻多的
推 PTTleader: 所有的NP問題都可以reduce成NP-complete的問題??
推 PTTleader: 沒事
→ yorunohoshi: 了解了，感謝a大～