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

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.

Package managers could stop being NP hard by taking away negative dependencies, including maximum version limits

> You took away the wrong thing

I'm more willing to believe they were taught the wrong thing.