作者h42318 (五兩三)
看板Grad-ProbAsk
標題[理工] NP-complete 102北科資工
時間Sun Feb 5 09:25:39 2017
http://i.imgur.com/ElNHa9i.jpg
各位好，
想請問第二小題，
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
→ yupog2003: reduce也要花時間，如果reduce要花O(n^4)的話就不代表 02/05 09:34
→ yupog2003: 所有NP都可以在O(n^3)解決了 02/05 09:34
→ yupog2003: 有NP-complete可在O(n^3)解決只能保證所有NP都可以在 02/05 09:35
→ yupog2003: polynomial time內解決而已，不一定是O(n^3) 02/05 09:35
推 ssssIssss: 只能證明能在polynomial-time內解決 02/05 10:27