News for hackers. Stuff that matters.
Re:NP-Complete Problems and Physical Reality (2005) by sqrt17 on Tuesday July 14, 2015 @07:40AM (#9884094)
A point that has become more obvious over the years is this: there are "soft" instances of NP-complete problems where you can find good approximations in reasonable time, and there are "crunchy" instances of the same class of problem where you don't find a good approximation.

Commercial ILP solvers (e.g. Gurobi, CPlex) profit from the fact that quite often it is possible to formulate NP-complete problems and find good solutions in acceptable time. Similarly, many of the "physical" ways of solving NP-complete problems work ok for easy instances and get unwieldly fast if confronted with difficult instances.

There are no comments on this comment yet.