作者haniwang (hani)
看板Grad-ProbAsk
標題[理工] NP
時間Mon Feb 11 08:21:41 2019
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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1549844504.A.72F.html
1F：推 feveral: True false 02/11 09:00
2F：推 TEPLUN: 都錯 02/11 09:08
3F：→ GeniusPuddin: 我聽課的理解是只要能多項式時間內互推就是一樣難? 02/11 09:08
4F：→ GeniusPuddin: 所以某個NPC可以n^3應該不保證其它也n^3內0.0? 求解 02/11 09:08
5F：→ GeniusPuddin: 2的話是不是要NPC才有保證 02/11 09:10
6F：推 zaq851017: 1. True 2. False 02/11 09:53
7F：推 zaq851017: 1.的話因為是NPC 所以所有NP可以reduce到它 所以它 02/11 09:55
8F：→ zaq851017: 上界是O(n^3)也保證其他NP ~~ 02/11 09:55
9F：→ zaq851017: 一個A 可以 reduce到 B B如果可以O(n^3)也可以保證A 02/11 09:56
10F：推 nannnnn: a也錯吧，reduce過去也要時間不是嗎?如果reduce要n^4轉換 02/11 09:59
11F：→ nannnnn: 時間，那不就沒辦法在n^3內解了 02/11 09:59
12F：推 zaq851017: 對齁沒考慮到這個XD 應該是樓上說得這樣 02/11 10:03
13F：推 ekids1234: 對 2 要 NPC NP不夠 頂多把該問題從NP踢出去 02/11 10:20