// HACKER NEWS — CYBERSECURITY
NP-Overrated
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.
For (1) and (2), the worst-case just doesn't occur.
I mean, installing packages and type checking can surely be slow.
But, at least in my career, I've never seen a galactic blow-up.
(3) and (4) are technically optimization problems.
Everyone knows you can tackle those with heuristics, but you don't have to sacrifice optimality.
We absolutely have tools that can find provably optimal solutions in reasonable time.
There's no magic.
No quantum computers.
Just thinking harder and coming up with better algorithms.
And that's what people have done.
In fact, algorithmic speedup has outpaced hardware gains in the last decades.
Taken together, this paper
cites a 450-billion-fold speedup between 1991 and 2015.