NP-Overrated

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.

[1]: https://en.wikipedia.org/wiki/Parameterized_complexity

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

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.

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.

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

A well known NP-hard problem is matching some flavors of regex (ex: PCRE). You can turn a 3-SAT problem into such a regex.

In normal situations, it is not a problem, I have written thousands of regex without ever hitting a galactic case (at least not one I am aware of).

But it can still be a problem because if the regex engine is too powerful and accepts user input, a specially crafted regex can be used as a denial of service attack.

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

Hehe, clearly the author hasn't written any SwiftUI.

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.

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

Ever since I first saw a binary integer program with millions of variables solved in less time than it took me to hit enter I realized that the fact that I had made it through graduate school for computer science, and never encountered the sorts of optimization algorithms happening in the field of operation operations research is a sad one.

One example is Sudoku. It's NP-hard, but in practice, it takes no time at all to solve your newspaper puzzle.

The author justifiably attacks the notion that "NP-hard" == "too hard to solve in practice", but then makes the opposite error:

> Everyone knows you can tackle those with heuristics, but you don't have to sacrifice optimality.

Unless you're using some weird definition of optimality, or happen to have a proof of N=NP in your back pocket: yes, yes you do.

You don't have to sacrifice "good enough". You don't have to let it run for an insane amount of time. Just about all interesting problems that I know of have either (1) good heuristics that in practice get close enough to optimal that nobody needs to care about the gap, or (2) constraints or restrictions that are totally fine to apply in practice.

But those are both ways of sacrificing optimality. You have to sacrifice optimality. It just turns out that optimality isn't usually very important, especially when 99% of optimality is achievable.

> We absolutely have tools that can find provably optimal solutions in reasonable time. There's no magic. No quantum computers. Just thinking harder and coming up with better algorithms.

No, we absolutely do not. Again, not unless someone has secretly come up with a constructive proof of P=NP. "Optimality" in the first sentence, "provably optimal" here, those terms are precise -- so I'm confused why the author is claiming that multiple people have achieved the impossible.

The article clears up one serious confusion only to replace it with another?

The general version of a problem being NP-complete doesn't mean that cases of practical interest are all necessarily intractable. In the case of SAT, for instance, there are also ways for the humans to give the solver an easier problem to solve in many cases, like adding extra clauses to guide the solver away from useless parts of the search space.

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.

A good deal of the field of Operations Research (OR) is about getting a good solution to NP-hard problems anyway. It is fun!

How come most package managers suck then? Why did I waste hours of my life debugging portage and yum?

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

Have you ever tried building an iOS app? The compiler gives up after a sufficient time because typechecking can be so slow

And if the problem is really really hard, you can throw an AI at it and hopefully get a probabilistic solution.

(not necessarily an LLM, AI is a huge field)

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

It's worth noting this cuts both ways. An NP-complete problem may wind-up having only a few instances that are exponential in the inputs but a problem that is "only" O(input-size^3) is going to be difficult to deal for input of significant size.

In the classic 1979 book "Computers and Intractability: A Guide to the Theory of NP-Completeness" by Garey & Johnson, here's how they explain what it means for the practicing programmer.

Chapter one starts with a fictional example. Say you have been trying to develop an algorithm at work that validates designs for new products. After much work you haven't found anything better than exhaustive search, which is too slow.

You don't want to tell your boss "I can't find an efficient algorithm. I guess I'm just too dumb".

What you'd like to do is prove that the problem is inherently intractable, so you could confidently tell your boss "I can't find an efficient algorithm, because no such algorithm is possible!".

Unfortunately, the authors note, proving intractability is also often very hard. Even the best theoreticians have been stymied trying to prove commonly encountered hard problems are intractable. That's where the theory of NP-completeness comes in:

> However, having read this book, you have discovered something almost as good. The theory of NP-completeness provides many straightforward techniques for proving that a given problem is “just as hard” as a large number of other problems that are widely recognized as being difficult and that have been confounding the experts for years.

Using the techniques from the book you prove the problem is NP-complete. Then you can go to your boss and announce "I can't find an efficient algorithm, but neither can all these famous people". The authors note that at the very least this informs your boss that it won't do any good to fire you and hire another algorithms expert. They go on:

> Of course, our own bosses would frown upon our writing this book if its sole purpose was to protect the jobs of algorithm designers. Indeed, discovering that a problem is NP-complete is usually just the beginning of work on that problem.

...

> However, the knowledge that it is NP-complete does provide valuable information about what lines of approach have the potential of being most productive. Certainly the search for an efficient, exact algorithm should be accorded low priority. It is now more appropriate to concentrate on other, less ambitious, approaches. For example, you might look for efficient algorithms that solve various special cases of the general problem. You might look for algorithms that, though not guaranteed to run quickly, seem likely to do so most of the time. Or you might even relax the problem somewhat, looking for a fast algorithm that merely finds designs that meet most of the component specifications. In short, the primary application of the theory of NP-completeness is to assist algorithm designers in directing their problem-solving efforts toward those approaches that have the greatest likelihood of leading to useful algorithms.

Once you admit approximations the theoretical problem trades places with a more interesting one: what is the Pareto frontier of loss vs complexity?

tl;dr NP-hard isn't that hard if you relax constraints.

While not novel its a pity warrants a legitimate HN front page.