3 ms·

> Many instances of NP complete problems are solved optimally all the time ... Okay, but the optimal solution of any NP-complete problem is still at least supe

> Many instances of NP complete problems are solved optimally all the time ... Okay, but the optimal solution of any NP-complete problem is still at least superpolynomial in complexity. If "optimally" also meant general-case computationally feasible (polynomial) we would have proved P=NP.

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 ago
  Excellent 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.
eru 1y ago
That's at most true for worst case instances, not necessarily for instances you will see in practice. Many instances of many NP-complete problems can be solved rather quickly in practice. Use an SMT solver or look into mixed integer linear programming solvers for some examples.