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.
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.
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..
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.
Comments
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.
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.
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..
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.