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)？
不知道這樣解釋對不對@@ 想請教大家想法 謝謝~