Is it possible for any of them to survive to P=NP, assuming that NP-complete O(2N) problems collapse to at best O(N2)?
Name:
Anonymous2011-07-18 7:13
>>17 The ``no'' was for Is it possible for any of them to survive to P=NP?Think again. Assuming that NP-complete problems start getting solved by O(N2) algorithms, even if you build a 3SAT out of the relationships between the variables, the runtime will still be O(N2) relative to the runtime of the verifier algorithm.