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