Hacker News Reader

Comment by jltsiren | Hacker News Reader

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.

View on HN

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

Once you start solving problems in practice, you are probably no longer interested in the simple clean versions of the problem theoreticians think about. For example, instead of trying to find the shortest common superstring, you may be doing phased genome assembly. The problem is no longer unambiguously defined. The constraints and assumptions evolve over time, as the problem space becomes better understood and the nature of the data changes. While algorithmic ideas often transfer from one problem subtype to another, everything needs to be tailored for the specific problem.

Reply on news.ycombinator.com