[理工] NP

[haniwang (hani)]

If an NP-complete problem can be solved deterministically in O(n^3),then every
 problem in NP can be solved in O(n^3).

If a problem that is in the class NP has a polynomial time solution,then P=NP.

請問上面這兩個敘述對嗎？

麻煩各位了！

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.139.0.113
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1549844504.A.72F.html
推 feveral: True false
推 TEPLUN: 都錯
→ GeniusPuddin: 我聽課的理解是只要能多項式時間內互推就是一樣難?
→ GeniusPuddin: 所以某個NPC可以n^3應該不保證其它也n^3內0.0? 求解
→ GeniusPuddin: 2的話是不是要NPC才有保證
推 zaq851017: 1. True 2. False
推 zaq851017: 1.的話因為是NPC 所以所有NP可以reduce到它 所以它
→ zaq851017: 上界是O(n^3)也保證其他NP ~~
→ zaq851017: 一個A 可以 reduce到 B  B如果可以O(n^3)也可以保證A
推 nannnnn: a也錯吧，reduce過去也要時間不是嗎?如果reduce要n^4轉換
→ nannnnn: 時間，那不就沒辦法在n^3內解了
推 zaq851017: 對齁沒考慮到這個XD 應該是樓上說得這樣
推 ekids1234: 對 2 要 NPC  NP不夠 頂多把該問題從NP踢出去