NP-hard problems are not as hard as you think
NP-Overrated
Many developers believe NP-hard problems are intractable, but in practice they're often solvable quickly. This post argues that worst-case complexity is rarely relevant, citing examples like package dependency resolution, type checking, scheduling, and SAT solving. It highlights algorithmic advances that have led to massive speedups, and notes that even Amazon solves a billion SMT problems daily.
In theory, there is no difference between theory and practice. But in practice, there is.
- pron
1. The study of complexity classes isn't intended to dissuade people from writing certain programs. It's intended to understand the nature and theoretical limits of computation. As far as practice goes, it can be used to show where heuristics are needed. Saying it's overrated is like saying calculus is overrated because most people don't need to use it every day. And BTW, many important problems are in classes believed to be way harder than NP (i.e. NP-complete is the easiest of the hard famous complexity classes). E.g., I've seen some people brag about some configuration language being easy to mechanically analyse because it's not Turing-complete, while in fact it's at least PSPACE-hard to analyse.
2. When there's some large set of instances of some NP-hard problem that are tractably solvable in practice (like SAT), the importance of that is that there's some non-NP-hard subset here. Indeed, SAT is FPT (fixed parameter tractable [1]), an "easier" type of NP, for which decomposition can help. In contrast, graph colouring is thought to not be FPT.
- Guvante
I feel like the write up doesn't really engage with the number one solution used
Don't allow the hard ones
Dependency managers tend to just block a huge category of situations that effectively eliminate the entire NP hard space
Type systems similarly are explicitly cordoned off
The trick isn't "do it anyway" beyond you kind of definitionly need to, it is to acknowledge the general problem is "impossible" so either do your best or start eliminating the impossible
- andrewla
Very true! What makes NP-hard problems difficult is almost always the combinatorial explosion related to specific problem configurations -- you can construct instances given an approximate heuristic or branch-and-bound solver that will cause it to have an exponential blow up. But for most practical problems you don't reach those explosive configurations.
There's probably a quantification of this in some sense for specific classes of NP-hard problems.
What's interesting is that many algorithms (especially in cryptography) are explicitly designed to create those combinatorial edge cases. A SAT solver looking at normal problems that occur in life and programming will do an amazing job. A SAT solver looking at SHA256, not so much. In fact, arguable the science of developing cryptographic systems is the science of finding these exponential explosions that are resistant to heuristic approximations.
- tux3
>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.
NP-hard problems are hard to solve exactly, but it's usually possible to get a pretty good approximate solution efficiently. But some search problems are just very hard, even approximately. If you've held an old Debian install through major upgrades with aptitude, you'll have had to see it get lost deep in outer search space pretty regularly.
Sometimes aptitude needs to downgrade a package, uninstall a package, or not install a recommended package to arrive at the right solution. There are many possible packages it could try to downgrade, and each of these creates a brand new mess with new possibilities. This is not something you get with other package managers, and its search strategy is genuinely intractable if you don't help it along by trying to manually figure out the small set of packages that create all the difficulty.
- jvanderbot
I'm fond of this brain-expander, in spirit of TFA: "Did you know travelling salesperson is O(N) on a large class of graphs?"
Another insight: I regularly find that clever O(logn) solutions are just obliterated by a few mostly-branch-free O(N) pre-passes followed by a problem that computers enjoy, like contiguous memory access and vector operations.
- not2b
I spent my career in electronic design automation, where practically every interesting problem is NP-hard, but we have to solve them, or approximately solve them at least, and because real-life problems often have structure, with the right approach very large problems can be solved exactly despite the theoretical complexity, and when exact solutions can't be found a decent bound can often be found that is an acceptable solution.
Sales people still have to plan their trips even though finding the optimal solution is NP-hard (to give one example). No matter; there are decent heuristic methods.
- chupasaurus
> 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.
Last time I had a galactic blow-up of apt solver (the final part of 64-bit time transition in Debian Testing) it was mere 2 GiB of memory per minute.
- lennoff
Sometimes you don't need an _exact_ solution. approximation of the traveling salesman problem exists for the metric version, it's O(n^3), and produces a result that's not worse than 50% of the optimal result, and for the general case O(n^2) algorithm exists that produces a result that costs at most twice the optimal result.