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.
請問上面這兩個敘述對嗎？
麻煩各位了！
作者: feveral (小漢堡) 2019-02-11 09:00:00
True false
作者:
TEPLUN (mihanami)
2019-02-11 09:08:00都錯
我聽課的理解是只要能多項式時間內互推就是一樣難?所以某個NPC可以n^3應該不保證其它也n^3內0.0? 求解2的話是不是要NPC才有保證
1. True 2. False1.的話因為是NPC 所以所有NP可以reduce到它 所以它上界是O(n^3)也保證其他NP ~~一個A 可以 reduce到 B B如果可以O(n^3)也可以保證A
作者: nannnnn (nannnnn) 2019-02-11 09:59:00
a也錯吧，reduce過去也要時間不是嗎?如果reduce要n^4轉換時間，那不就沒辦法在n^3內解了
對 2 要 NPC NP不夠 頂多把該問題從NP踢出去