NP-overrated
This title could be clearer and more informative.Try out Clickbait Shieldfor free (5 uses left this month).
NP-hard problems are often assumed to be practically unsolvable, but the author argues this reputation is overstated. Real-world worst-case blow-ups rarely occur for problems like dependency resolution and type checking, while optimization problems like scheduling and traveling salesman can be solved optimally with modern solvers (Gurobi, SCIP, OR-Tools). Even SAT and SMT, considered archetypal NP-hard problems, are solved at massive scale today - Amazon reportedly runs a billion SMT queries a day - thanks to decades of algorithmic improvements that have outpaced hardware gains (a cited 450-billion-fold speedup between 1991 and 2015).
Questions this post answers
Does NP-hard mean a problem is basically impossible to solve in practice?
No, NP-hardness describes worst-case complexity, not practical difficulty. Many NP-hard problems like dependency resolution, type checking, and scheduling are solved efficiently in practice because worst-case inputs rarely occur or heuristics combined with modern solvers find optimal solutions in reasonable time. For engineers weighing whether an NP-hard bottleneck is actually a real risk, daily.dev surfaces practical takes like this on algorithmic complexity.
How many SMT problems does Amazon solve per day?
Amazon solves roughly a billion SMT (Satisfiability Modulo Theories) problems a day, according to Amazon Science. SMT is considered a harder variant of Boolean satisfiability (SAT), and the fact that it runs at this scale shows how far SAT/SMT solver performance has advanced despite the underlying problem being NP-hard. Developers evaluating SAT/SMT solvers at scale can find grounded examples like this through daily.dev.
How much have algorithms for optimization problems improved compared to hardware speedups?
Algorithmic improvements for certain optimization problems have outpaced hardware gains, with one cited paper reporting a 450-billion-fold speedup in best subset selection algorithms between 1991 and 2015. This suggests that better algorithms, not just faster chips, are what made previously impractical NP-hard optimization problems solvable at scale. Anyone tracking how algorithmic progress changes what's feasible can follow discussions like this on daily.dev.