A provocative essay titled "NP-overrated" hit 224 points on Hacker News this week, and it makes a point that every developer should internalize: "NP-hard" doesn't mean "impossible." In practice, most NP-hard problems that developers actually encounter are tractable — and treating them as intractable is a costly mistake.
The Myth of NP-Hardness
The essay's author, writing under the name Gruhn, opens with a familiar scene: a computer science professor delivering the final lecture with dramatic words:
"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."
The theory isn't wrong. NP-hard problems are, in the worst case, intractable. But the essay argues — persuasively — that in practice, the worst case rarely occurs. And building your engineering decisions around the worst case is a form of premature optimization that costs real productivity.
Five Prominent NP-Hard Problems That Work Fine in Practice
The essay lists several NP-hard problems that developers encounter regularly:
1. Dependency Resolution (Package Managers)
Every time you run npm install or pip install, the package manager solves an NP-hard problem: finding a consistent set of versions that satisfies all dependency constraints. In theory, this can blow up exponentially. In practice, package managers like npm, pip, and cargo resolve dependencies in milliseconds for 99.9% of real-world projects.
2. Type Checking
Type checking in many type systems is NP-hard. Yet TypeScript, Rust, and Haskell all perform type checking on millions of lines of code in reasonable time. The worst-case inputs simply don't arise in practice.
3. Traveling Salesman Problem (TSP)
The canonical NP-hard problem. In theory, finding the optimal route between N cities requires O(N!) time. In practice, the Concorde TSP solver finds provably optimal solutions to problems with tens of thousands of cities. For typical logistics problems, the solution is found in seconds.
4. Boolean Satisfiability (SAT)
SAT was the original NP-complete problem. In theory, it's as hard as any problem in NP. In practice, modern SAT solvers (like MiniSat, Glucose, and CaDiCaL) solve instances with millions of variables. The SAT competitions have driven solver performance to the point where SAT is now considered "the easy part" of many verification pipelines.
5. Satisfiability Modulo Theories (SMT)
SMT is an even harder version of SAT — it adds theories like linear arithmetic, arrays, and bitvectors. Yet SMT solvers like Z3 are used routinely in program verification, constraint solving, and automated theorem proving. They solve problems that are theoretically intractable on a regular basis.
Why Practice Defies Theory
The essay identifies several reasons why NP-hard problems are often tractable in practice:
Algorithmic Speedup Outpaces Hardware
It's well known that hardware improvements have driven massive performance gains. Less well known is that algorithmic improvements have outpaced hardware gains in many domains. The essay cites a 450-billion-fold speedup in combinatorial optimization between 1991 and 2015 — most of which came from better algorithms, not faster computers.
Worst-Case Inputs Are Rare
The theory says there exist inputs that cause exponential blow-up. The practice says those inputs almost never occur in real-world workloads. The gap between theory and practice is enormous:
- Package dependencies in real projects form sparse graphs with limited version constraints
- Type checking on real code rarely triggers the pathological cases
- TSP instances from logistics have structure (planarity, triangle inequality) that solvers exploit
- SAT instances from hardware verification have structural properties that modern solvers exploit
Heuristics Work Surprisingly Well
For optimization problems where provable optimality isn't required, heuristics often find near-optimal solutions in polynomial time. For many practical purposes, a solution that's within 1% of optimal is just as good as the optimal solution — and it can be found in milliseconds instead of years.
Timeouts Are a Safety Net
The essay makes a practical point that's often overlooked:
"But what if you run into the worst-case? You don't have to wait for the heat-death of the universe. An HTTP request also doesn't come back sometimes. Add a timeout, show an error message, ... you know the drill."
This is the engineering answer to the theoretical concern. If your SAT solver or TSP solver or dependency resolver occasionally hits a pathological case, you handle it the same way you handle any other timeout: with a timeout, error message, and fallback strategy. You don't design your entire system around the worst case.
The Cost of Overestimating Difficulty
The essay's most important point is about the cost of treating tractable problems as intractable:
If a developer hears "NP-hard" and immediately reaches for an approximation algorithm or a heuristic, they may:
- Miss the optimal solution that a exact solver would have found in seconds
- Add unnecessary complexity by implementing custom heuristics
- Waste time optimizing for a worst case that never occurs
- Avoid solving the problem entirely when it was perfectly solvable
The real-world cost of "NP-hard anxiety" is measured in missed opportunities, over-engineered solutions, and abandoned projects.
Practical Recommendations
Based on the essay's arguments, here's a practical framework for developers:
Try the exact solution first. Many NP-hard problems can be solved exactly for real-world input sizes. Don't assume you need an approximation.
Use modern solvers. SAT solvers, SMT solvers, ILP solvers, and constraint programming engines have gotten dramatically better. Tools like Z3, OR-Tools, and Gurobi can solve problems that would have been considered intractable a decade ago.
Add timeouts. If the exact solver doesn't finish in 30 seconds, fall back to a heuristic. This gives you the best of both worlds: optimal solutions when they're achievable, approximate solutions when they're not.
Understand your input distribution. The theory says worst cases exist. The practice says your inputs probably aren't the worst case. If you understand the structure of your actual inputs, you can choose the right approach.
Don't let "NP-hard" stop you. It's a theoretical label, not a practical verdict. Many of the most useful systems in software engineering solve NP-hard problems every day, quickly and reliably.
The Meta-Lesson
The essay's most quoted line captures the essence:
"In theory, there is no difference between theory and practice. But in practice, there is."
Computer science education teaches us to respect complexity theory — and we should. But it should also teach us that complexity theory describes the worst case, not the typical case. The gap between theory and practice is where engineering lives, and that gap is often enormous.
The next time someone says "that's NP-hard" as if it ends the conversation, remember: NP-hard is a theoretical label. Whether the problem is actually hard depends on your inputs, your algorithms, and your engineering constraints. In practice, "NP-hard" often just means "solvable, with a timeout."
Based on "NP-overrated" by Gruhn.
Top comments (0)