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踢出去