3 ms·
And equally if "the optimal solution of any NP-complete problem is still at least superpolynomial in complexity" were true then we would have proven P!=NP..
by HappMacDonald 1y ago
And equally if "the optimal solution of any NP-complete problem is still at least superpolynomial in complexity" were true then we would have proven P!=NP..
- daveguy 1y agoExcellent point. "Any" and "at least" were overstated. Should have been "all so far." But I'm definitely going with the side where we have all the evidence so far (even if it isn't proof) when deciding expectations in the next few decades at least.