'It's NP-Hard, So Give Up' Is a Myth That Doesn't Survive Contact With Practice

A common lesson from computer science courses is that NP-hard problems are effectively hopeless: solvable in theory, but so expensive that no practical algorithm exists. The author argues this framing is misleading. The worst-case complexity that makes these problems ‘hard’ rarely shows up on real inputs. An algorithm can blow up on some pathological case while still returning fast answers on 99.9% of inputs — or on every input anyone actually cares about — and the theory does nothing to rule that out.

Concrete examples make the point. Dependency resolution in package managers and type checking are technically NP-hard, yet in ordinary use they essentially never hit catastrophic slowdowns. Scheduling and Traveling Salesman are optimization problems where modern solvers routinely find provably optimal answers in reasonable time — no heuristics-only compromise and no quantum computing required, just decades of better algorithms. The author notes that algorithmic progress has actually outpaced hardware gains, citing a paper that measured a roughly 450-billion-fold speedup on one problem between 1991 and 2015. Even Boolean satisfiability, the textbook NP-hard problem, is now solved at massive scale: Amazon reportedly runs about a billion SMT queries a day, and SAT solving has become the easy part of that harder problem.

The practical takeaway is that ‘it’s NP-hard’ is not a valid reason to declare a problem unsolvable. Real systems built on these problems work fine, and for the rare worst-case input the fix is mundane engineering — set a timeout and return an error, the same way you’d handle an HTTP request that never comes back. Treating theoretical intractability as a hard wall discourages people from building things that are entirely feasible.