Breaking public key cryptosystems would be a better counterexample. Most NP-hard optimization problems can be solved in practice. While there are always some degenerate instances nobody knows how to handle, realistic instances tend to be easy enough to solve or at least approximate accurately.
> Breaking public key cryptosystems would be a better counterexample.
I deliberately avoided giving that example. Calling that a positive contribution to humanity and expecting credit for it feels a bit like calling the atomic bomb a positive contribution to humanity and expecting credit for it. Much of the world would rather stay away from that timeline.
> Most NP-hard optimization problems can be solved in practice.
Hence "a solution that is empirically sufficiently faster than the state of the art" and not merely "a solution".
loading story #50334384