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

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.

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

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

Don't allow the hard ones makes the problems P doesn't it?