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.

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

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.

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

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.

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.

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.

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

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

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.

Perfect example is the simplex algorithm.

We do have a polynomial algorithm for linear programming yet simplex (with exponential worst case performance) is our tool of choice.

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

The algorithms listed were intentionally chosen to be easy to solve.

Calculating general equilibrium over non divisible goods is NP hard. It is practically infeasible because your problem size is eight billion people each choosing from hundreds of millions of products to produce or consume.

Another problem is basically any form of non convex optimization because even the approximations require describing a non convex polygon as piecewise linear segments and therefore even the approximation algorithm are NP hard.

Now you will probably be like "what's the big deal? Just solve it like any other NP hard problem, with brute force. You only need to solve it once to prove that it is solvable."

Unfortunately this theoretical ability to solve a problem is useless in practice, because you need to solve the problem frequently. Let's say a thousand times per second. Yes, you only have a millisecond to solve the problem and you must produce an answer within that deadline.

In practice everyone has given up and uses QP approximations instead, disproving the premise of the article. You are better off with memorization based systems that classify the situation and then choose a memorized answer, like neural networks, and only after that do you actually try to use the QP solver to refine the solution. So yeah, if you build a machine like that you're throwing your hands up a thousand times per second saying "can't be done".

I'm sort of in this boat right now. I wrote an algorithm to solve a problem, and it turns out to be roughly O(n!), which is really terrible, but it works fine in all my test cases because n never gets bigger than 20. Even in real life cases, I doubt n will ever be larger than 40 (which is where it starts to break down).

I'm still going to look for a more efficient way to do it, but sometimes you can go a long way without scaling. Not everything needs to scale to large numbers.

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

A lot of simulation we only have exponential-time algorithms for. Motion planning, protein folding, etc. For a lot of these today, the SOTA is to use an NN model to learn the heuristics from data. OP's claim only rings true if one can only think of just the algorithms that undergrad CS now studies.

When people are initially confronted with TSP and similar optimization problems, the reaction is usually awe at the shear number of potential combinations. "A 48 city tour of the continental US has 10^61 possibilities!!".

Well, not really. Massive chunks of the search space can be eliminated through clever (but non-optimal) algorithms. The rest of the search space can usually be explored through heuristics. In practice, we can solve gigantic TSP problems "well enough" and "fast enough".

It reminds me of the Midwit meme. Both the low IQ and high IQ folks say "Heuristics are good enough". Only the mid IQ guy cares about NP-hard.

That's not to take away from the research into theoretical limits of computation. Just noting that's a completely different question from the practical concerns of actually solving those problems IRL

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

Honestly, this is what makes computer science fun.

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.

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.

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

> 2. Type checking (not all type systems)

> For (1) and (2), the worst-case just doesn't occur.

I don't think 2. is a good example to be honest, It happens quite a lot. At least it's definitely not in the same category as dependency resolution, where people often don't even know that it's NP-hard.

Typescript, Rust or C++ type system complexity is routinely a compile time problem that people have to work around or tackle from both sides (i.e. either changing the compiler or changing the program).

I've made comments on HN on this point a number of times e.g. https://news.ycombinator.com/item?id=44284083

I had some tedious debate on HN once where I asked if anyone had any pointers to good parallel SMT solvers, only to fall victim to someone dedicated to dying on the hill of "parallelization can never make this kind of search faster" due to (often inapplicable) complexity theory fixation.

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

I have, it's called conda.

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

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.

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

Just an example: Klondike (the solitaire game) is NP-hard (and, if I remember correctly, NP-complete) and it never stopped players from playing it, or developers from implementing it, even though it's sometimes impossible to know if the given setup has a solution at all, or not.

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.

> 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

Reminds me of Rich Hickey's clojure data structures. Yes, they're technically log_32(n) complexity, but it turns out log 32 is basically flat on any normal machine, thus "practically constant".

This is kind of why P vs NP is such an interesting problem. It seems that a big family of NP-hard problems in fact _can_ be solved efficiently if we allow relaxing some constraints, like optimality (eg TSP), or generality of our algorithm (eg type checking).

I feel that is similar to how adding randomness to cryptography [1] opened a bunch of new systems like zero knowledge proofs[2]. By allowing us to be wrong in a very small number of instances (arbitrarily small by adjusting things like key size), we can build practical systems with really impressive properties.

[1]: Goldwasser and Micali - Probabilistic Encryption, 1983 https://web.archive.org/web/20090319000035/http://groups.csa... [2]: Goldwasser, Micali and Rackoff - The knowledge complexity of interactive proof-systems, 1985 https://courses.csail.mit.edu/6.857/2008/handouts/1989-siamj...

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)

Did you know: general purpose computers are completely pointless, because programs can run forever without producing a result.

I mean, yeah? I guess they could make more clear that their perspective is as theoretical computer scientists.

I don't think their aim is to dissuade people from running approximate optimization against np. At least that was certainly never my takeaway, but maybe some courses/lecturers don't make that clear enough.

If your larger point is that comp sci cares too much about theory for the average programmer, sure. Maybe there should be a different degree program for software "engineering". But I think that's true of most degrees. Maybe comp sci is special because it's treated as a science whereas most people take it to be engineers. But coming from physics as just an example, the majority of people become engineers or something else not-professional-physics. But I sure as hell hope they don't go less proof-heavy in physics courses because many people will never never be able to prove something again in their lives.

Traveling salesman solution within 2N for optimal solution length N is trivially solvable for K^2log(K) for K places. Just make the minimal spanning tree and do a loop of it.

A lot of professors don't teach this, and it's recklessly ignorant if not worse.

> For [Dependency resolution] and [Type checking], the worst-case just doesn't occur. ... at least in my career, I've never seen a galactic blow-up.

Both of these problems have been hand crafted and sanded down so as not to get into situations where there's exponential blow up.

> [Scheduling] and [Traveling Salesman] are technically optimization problems. Everyone knows you can tackle those with heuristics, ... 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. ... algorithmic speedup has outpaced hardware gains in the last decades. ...

The tools that can "absolutely find optimal solutions" don't, for even toy problems. Thinking harder helps, sometimes, but barely scratches the surface of most of these problems. Most of the time, thinking harder doesn't magically solve these problems.

> Last but not least: even (5), the archetype of NP-hard problems, is routinely solved at scale.

If this were even remotely true we'd have seen substantial progress in automated theorem proving well before the last couple of years. Notice how there are many math problems succumbing to automated techniques? This isn't because SAT solvers "routinely solve this at scale", it's because LLMs are getting better.

Why do we need type checking in the first place? One reason is to help find bugs. We need to enforce type checking to reduce bugs because reducing programs to SAT to ensure they're bug free is intractable. SAT is solved at scale? Why haven't they made solvers to prove your code is bug free so you don't need type checking in the first place?

I'm not up on scheduling software or research but my bet is that people who actually write schedulers would say that those tools that "absolutely" solve the problem absolutely don't.

The post almost gets it but never quite makes the leap. Taking Turing machines, for example. It's pretty easy to show that the Halting problem is undecidable. It doesn't mean all programs can't be analyzed, it means that there's no general method that will work for all programs. We don't give up on writing programs, we restrict ourselves to programs that we can reason about.

The ensemble, the space of problems we draw from, is specifically chosen so that we can do interesting work. But even that's restrictive and we're trying to constantly push to see what other programs we can analyze that are past our current front of knowledge.

This reads like child going into a supermarket and declaring farming, logistics and food scarcity to be solved because of the abundant availability of goods on the shelf. The world we've made is specifically crafted so that normal use is smooth. The fact you can't see it means you're living in a coddled domain and haven't pushed past it.

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