3 ms·
> No one has ever found an efficient algorithm for an NP-complete problem, and most computer scientists believe no one ever will. I find these kinds of asserti
by dcohenp 11y ago
> No one has ever found an efficient algorithm for an NP-complete problem, and most computer scientists believe no one ever will.
I find these kinds of assertions somewhat misleading. There _are_ "efficient" algorithms for, one could say, "pragmatic variations" of NP-complete problems. Some only work on some subset of cases (perhaps most of the useful ones), or non-deterministic (but you run them enough times and get the right answer), etc.
- username223 11y agoThis. MJD has a great bit on blanket statements about "NP-complete means hard": http://perl.plover.com/yak/12views/samples/notes.html#sl-24 Basically, you can often either settle for slightly suboptimal solutions, or ignore a few pathological worst cases. That said, I suspect that P != NP, and thought this was a good article.