GoKawiilNP-overrated Aug 13, 2026
If you learned about NP-hard problems in university, your takeaway was probably this:
NP-hard problems are solvable in theory but it's hopelessly expensive in practice. It's basically proven that no good algorithms exist.
At least that's what I took away. And almost everyone I've talked to. And many people online. I keep seeing "No you can't do it. It's NP-hard. Blah blah" discussions. The myth is pervasive but these problems are not intractable.
At the time, my professor closed the final lecture with dramatic words (I'm paraphrasing slightly):
And now you've learned that almost all interesting problems are undecidable and of the remaining ones, almost all are NP-hard. For the project of computer science, that puts the final nail in the coffin.
Sheesh. Not sure if everyone got such a dire framing but that would explain.
The theory is not wrong, but in practice it's often irrelevant. Sure, any algorithm you can come up with will blow up on some inputs. But you might get a fast solution on 99.9% of inputs. Or 100% of the remotely relevant inputs. The theory does not rule that out.
In theory, there is no difference between theory and practice. But in practice, there is. -- Benjamin Brewster
A few prominent NP-hard problems:
... continue reading