[理工] NP

看板Grad-ProbAsk作者 (hani)時間6年前 (2019/02/11 08:21), 編輯推噓7(7推 0噓 6→)
留言13則, 6人參與, 6年前最新討論串1/1
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
推
02/11 09:00, 6年前 , 1F
True false
02/11 09:00, 1F
推
02/11 09:08, 6年前 , 2F
都錯
02/11 09:08, 2F
→
02/11 09:08, 6年前 , 3F
我聽課的理解是只要能多項式時間內互推就是一樣難?
02/11 09:08, 3F
→
02/11 09:08, 6年前 , 4F
所以某個NPC可以n^3應該不保證其它也n^3內0.0? 求解
02/11 09:08, 4F
→
02/11 09:10, 6年前 , 5F
2的話是不是要NPC才有保證
02/11 09:10, 5F
推
02/11 09:53, 6年前 , 6F
1. True 2. False
02/11 09:53, 6F
推
02/11 09:55, 6年前 , 7F
1.的話因為是NPC 所以所有NP可以reduce到它 所以它
02/11 09:55, 7F
→
02/11 09:55, 6年前 , 8F
上界是O(n^3)也保證其他NP ~~
02/11 09:55, 8F
→
02/11 09:56, 6年前 , 9F
一個A 可以 reduce到 B B如果可以O(n^3)也可以保證A
02/11 09:56, 9F
推
02/11 09:59, 6年前 , 10F
a也錯吧，reduce過去也要時間不是嗎?如果reduce要n^4轉換
02/11 09:59, 10F
→
02/11 09:59, 6年前 , 11F
時間，那不就沒辦法在n^3內解了
02/11 09:59, 11F
推
02/11 10:03, 6年前 , 12F
對齁沒考慮到這個XD 應該是樓上說得這樣
02/11 10:03, 12F
推
02/11 10:20, 6年前 , 13F
對 2 要 NPC NP不夠 頂多把該問題從NP踢出去
02/11 10:20, 13F
‣ 更多 haniwang 的文章
文章代碼(AID): #1SOC0OSl (Grad-ProbAsk)