2 ms·
> What’s interesting about NP-hard problems is that they are mathematically equivalent. So a solution for one automatically implies a solution for them all. Th
by baddox 12y ago
> What’s interesting about NP-hard problems is that they are mathematically equivalent. So a solution for one automatically implies a solution for them all.
That's a mistake. The author is describing NP-complete problems, which are all roughly equivalent (reducible in polynomial time). NP-hard includes all NP-complete problems, but also includes problems much harder than those in NP-complete, including undecidable problems like the halting problem which aren't even in NP.
- pcvarmint 12y ago> That's a mistake. The author is describing NP-complete problems... Correct. I think that quote basically killed the whole article for me.
- baddox 12y agoIt didn't kill the whole article for me, although it seems to be a consistent misconception rather than an isolated typo. To be fair, the naming convention is pretty tricky, considering NP-hard contains things outside NP.
- icodestuff 12y agoAnd the diagram did get the terminology right. The author may need a (better) proofreader, but it wasn't impossible to see what the author meant. They only conflated the names, not the concepts.