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

Presumably the ones where you are expected to have the latest version of everything and make a new package if you break that (python2 → python3)

Not sure why more ecosystems don't do this. Sure an update could break dependents, but, like, you already have a big problem if a dependent was keeping you on an old version no matter what.

Building a SAT solver into the package manager seems to be a solution in search of a problem.