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