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.
請問上面這兩個敘述對嗎？
麻煩各位了！

True false

都錯

我聽課的理解是只要能多項式時間內互推就是一樣難?所以某個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

a也錯吧，reduce過去也要時間不是嗎?如果reduce要n^4轉換時間，那不就沒辦法在n^3內解了

對齁沒考慮到這個XD 應該是樓上說得這樣

對 2 要 NPC NP不夠 頂多把該問題從NP踢出去