Join the discussion
Write your take first — we'll ask for email only when you're ready to publish.
- Hacker News
- This dovetails into one of my favorite CS sub-fields: approximation algorithms. In many cases NP-Hard problems may be approximated with a guaranteed lower bound of accuracy. For example, solving the euclidean version of the travelling salesman problem using a minimum spanning tree finds solutions that are no worse than 1.5 times the true minimum length, and there are heuristics with weaker guarantees that consistently perform better in practice.by hingler36
- That is proximal to one of my peeves in this space: People who misunderstand approximation results to be meaningful when often they're not.
For example, the minimum set cover problem shows up in cases like "What minimal set of test vectors covers all the conditions in my code?". There is an obvious greedy algorithm: "Start with nothing, pick the vector that covers the most yet-uncovered cases, repeat until all are covered".
There is an approximation result that says no polynomial time algorithm can do more than a small factor better than this greedy algorithm.
But this is a _worst case_ result, and absolutely useless for any problem you will encounter in practice.
It's trivial to come up with ways of improving the greedy algorithm: First off the simple greedy algorithm will often produce output which has completely redundant elements that can just be removed, because some collection of later added items that were necessary to cover some rare cases completely cover some earlier added item. Adding a simple postprocess to remove redundant elements immediately improves the greedy solution, particularly when the frequency of elements follows something power-law ish.
You can measure the frequency of each element and weigh uncovered elements by how rare they are (E.g. using entropy). This avoids the primary cause of the above duplicate selections.
You can use lookahead e.g. pick the pair of elements that together improve the score the most but then only commit to one.
You can use rarity weighed random starts, complete using whatever search you have, then retry multiple times.
You can compute new solutions using only the results of prior attempts. etc. etc.
In my experience basically any improvement over the greedy algorithm works on real problems, even before getting to a proper ILP solver. The greedy algorithm is just pathetic and will result in solutions much worse than you get from simple elaborations.
But over and over again you can find people being told to use the greedy algorithm because no polynomial time algorithm is better -- even in instances that are small and where actually enumerating all solutions might be tractable and justified.
by nullc - > A few prominent NP-hard problems:
> Type checking (not all type systems)
> 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.
Swift was infamous of having exponential time type inference that made expressions like `"foo" + "bar" + "baz" + "qux" + 123` take literal minutes to fail with a compiler error.
by murderfs - > 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.
by chupasaurus - Exactly.
Debian allow you to choose different solver (typical Debian). It is easy to get galactic blow up if you insist.
by j16sdiz - 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.by lennoff
- If you allow twice the solution, you can do it in O(m log n) time using MST.by JohnKemeny
- Twice the optimal result is terrible, though.
Luckily, there are pretty good heuristic solutions that work well in practice.
by hyperpape - For traveling salesman that's more than good enough. But in many cases an O(n^3) algorithm can't be used because n is in the billions. I remember interviewing a candidate who asserted that register retiming in digital circuits was a non-problem, so they were surprised that we were still working on improvements, because they had learned that the Leiserson-Saxe algorithm gives an optimal solution in O(n^3) time. But because real circuits are so large that that approach can't be used. Polynomial time often isn't good enough; even quadratic time often isn't tolerable.by 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.
by not2b - Funnily enough this very morning I asked an LLM to implement an algorithm for an NP-hard problem (a variation of the knapsack problem). I gave it 2 directives:
* Do not implement an np solution trying to get the perfect score. Implement a fast solution that gets within x% of optimal
* If a solution seems impossible or it takes too long, return the closes solution you can find, and a warning about the solution being suboptimal
I got the code in a few minutes. On a sample of random inputs, the algorithm produces a solution within 1% of optimal in ~99.9% of the cases. p95 execution time is well below 2ms in my laptop.
That's it, that's everything you need for a production system. "close enough" very fast is sufficient, and the impossible cases very rarely happen. Even when they do, you can simply work around them.
by angarg12 - > 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.
You took away the wrong thing. The theory tells you that no good algorithm exists for _all_ possible inputs. This means you have to try to limit yourself to a subset of the problem space, and use heuristics to move all the remaining pathological cases (if any) to a corner you then monitor and ensure doesn't occur in practice too often.
Package managers are designed the way they are _because_ of the inherent NP-hardness, not _despite_ it as this article conveys.
In the formal models of dependency resolution, the three core conditions are: 1) Root package is included, 2) Dependency closure (everything required is present) 3) Version uniqueness (at most one version per package name)
NPM, yarn etc drop 3) which makes it not NP hard.
Go limits itself to minimum version selection which admits a linear time solution.
Cargo allows multiple major versions, thus reducing most cases of 3), and then relies on heuristics to prune and reduce the pathological cases to be relatively rare. There have been cases of real world trees that had issues, but then you add a heuristic that catches that type, and then eventually it becomes super rare. This style of design is adopted because of the known NP-hardness. We don't go around looking for algorithms to solve the general case, and we simplify the problem where possible knowing the benefit we get in return, or we watch and shift around the pathological cases to a rare corner, all because of knowing it is NP hard.
Amazon's SMT solvers and similar all use in principle similar tricks - only passing simplified encodings, portfolio solving i.e Promise.any(multiple solvers with same problem), timeouts + fallback, etc.
Another common example is the MIPs used by food delivery and other gig platform companies where the complexity of the solver is intentionally and aggressively slashed using as many tricks as possible.
- > You took away the wrong thing
I'm more willing to believe they were taught the wrong thing.
by BigTTYGothGF - Package managers could stop being NP hard by taking away negative dependencies, including maximum version limitsby inigyou
- > NPM, yarn etc drop 3) which makes it not NP hard.
A minor point, but npm peer dependencies mean that in theory it actually is NP-hard! Even if it's rarely exhibited in practice.
by ryangibb - In Python there are definitely times with large environments where you get combinatorial corners where things go exponential -- at scale processing user workloads and environments we've definitely hit sharp corners here. Switching to better and faster resolution systems have improved things significantly (because even the exponential case reduces to wall-clock times that aren't terrible) but you definitely hit those corners because Python is very architecturally bad for how it specified package dependencies.by andrewla
- 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.
by jvanderbot - Do you have any examples of the second class?by momojo
- Yeah why is "the algorithm" the thing we do in our head to mimick a 1970s computer and not what really happens on hardware.by hahahaa
- >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.
by tux3 - The description you've given for apt just sounds almost exactly like SAT, a problem that's very efficiently approximated. That's exactly how the --solver 3.0 flag on recent apt versions works [0].
- 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.
by andrewla - I think the phrase you're looking for is the phase transition.
Discussed here: https://cstheory.stackexchange.com/questions/33550
by JohnKemeny - 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
by Guvante - > Dependency managers tend to just block a huge category of situations that effectively eliminate the entire NP hard space
Can you elaborate on this? Many _try_ to get around this, e.g. Cargo's https://doc.rust-lang.org/cargo/reference/resolver.html#semv..., but it's not quite in P. Nix offloads dependency resolution to *2nix tools. Go's minimum version selection is just a tree walk, but it loses a fair amount of expressivity.
by ryangibb - Don't allow the hard ones makes the problems P doesn't it?by silasdavis
- A variant:
> Don't encounter the hard ones
For example, with the simplex method for linear programming, we don't do anything about disallowing the hard instances. We just solve the problems as they come in and none of the ones we get asked to solve ever turn out to be hard. (Generalizing, of course.)
by bo1024 - Another way to look at it is that in practice N is typically bounded by a large constant, making the time complexity effectively O(1).
For dependency resolution specifically, the set of possible dependencies is probably in the range 100 - 10000 for all ecosystems, even if the number of available packages in an ecosystem continues to grow.
by stabbles - 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.
by pron - > It's intended to understand the nature and theoretical limits of computation.
Not in a general sense, at least for standard complexity theory. It only deals with a very specific model of computation. Anyone with a sufficiently solid grasp of metamathematics intuitively understands that the distinction between solve and verify is nothing but a description of how badly matched our foundations are for the structure we're trying to view.
... This is the second time today I've posted about foundations like this.
by ux266478