[理工] NP-complete 102北科資工
各位好，
想請問第二小題，
NP-Complete的定義：A屬於NP且屬於NP-hard，NP-hard的定義是所有屬於NP的問題都可以reduced to NP-hard，所以NP-complete問題可在O(n^3)解決，不就是代表NP也可以在O(n^3)解決嗎？
不知是哪裡想法有誤@_@
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 120.126.194.203
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1486257941.A.88F.html
→
02/05 09:34, , 1F
02/05 09:34, 1F
→
02/05 09:34, , 2F
02/05 09:34, 2F
→
02/05 09:35, , 3F
02/05 09:35, 3F
→
02/05 09:35, , 4F
02/05 09:35, 4F
推
02/05 10:27, , 5F
02/05 10:27, 5F