NP-overrated

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).

Nguồn: https://gruhn.me/blog/2026-08-13. 8 Sync News chỉ tóm tắt và dẫn link; bản quyền nội dung thuộc tác giả và nguồn gốc.