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)？
不知道这样解释对不对@@ 想请教大家想法 谢谢~