3 ms·
In particular, impossibility results do not rule out approximate solutions that are good enough for practical purposes.
by lisper 9y ago
In particular, impossibility results do not rule out approximate solutions that are good enough for practical purposes.
- thomasahle 9y agoUnless it is an "impossibility of approximation" theorem.
- fmap 9y agoEven that is frequently misleading. Take the problem of finding a maximum independent set. You can show that if you manage to approximate this problem within any constant factor then P = NP. On the other hand, finding large independent sets is a common subproblem in several graph reduction algorithms and simple heuristics often work very well on the graphs that occur in practice.