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.

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.

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

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

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