NP-overrated
NP-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.<br>It's basically proven that no good algorithms exist.
At least that's what I took away.<br>And almost everyone I've talked to.<br>And many people online.<br>I keep seeing "No you can't do it. It's NP-hard. Blah blah" discussions.<br>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.<br>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.<br>Sure, any algorithm you can come up with will blow up on some inputs.<br>But you might get a fast solution on 99.9% of inputs.<br>Or 100% of the remotely relevant inputs.<br>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:
Dependency resolution (in package managers)
Type checking (not all type systems)
Scheduling
Traveling Salesman
Boolean Satisfiability (SAT)
For (1) and (2), the worst-case just doesn't occur.<br>I mean, installing packages and type checking can surely be slow.<br>But, at least in my career, I've never seen a galactic blow-up.
(3) and (4) are technically optimization problems.<br>Everyone knows you can tackle those with heuristics, but you don't have to sacrifice optimality.<br>We absolutely have tools that can find provably optimal solutions in reasonable time.<br>There's no magic.<br>No quantum computers.<br>Just thinking harder and coming up with better algorithms.<br>And that's what people have done.<br>In fact, algorithmic speedup has outpaced hardware gains in the last decades.<br>Taken together, this paper<br>cites a 450-billion-fold speedup between 1991 and 2015.
Last but not least: even (5), the archetype of NP-hard problems,<br>is routinely solved at scale.<br>Amazon is solving a billion SMT problems a day.<br>SMT is an even harder version of SAT.<br>The SAT algorithms have gotten so good,<br>it's now considered the easy part.
But what if you run into the worst-case?<br>You don't have to wait for the heat-death of the universe.<br>An HTTP request also doesn't come back sometimes.<br>Add a timeout, show an error message, ... you know the drill.