Миф об NP-трудных задачах: почему они решаемы на практике

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. -- Benjamin Brewster A few prominent NP-hard problems: - Dependency resolution (in package managers) - Type checking (not all type systems) - Scheduling - Traveling Salesman - Boolean Satisfiability (SAT) 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 always have to sacrifice optimality. We absolutely have tools that can often 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. Last but not least: even (5), the archetype of NP-hard problems, is routinely solved at scale. Amazon is solving a billion SMT problems a day. SMT is an even harder version of SAT. The SAT algorithms have gotten so good, it's now considered the easy part. 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.