> 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)
I'm curious, which formal models of package management are you referencing?
> 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.
> 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)
This is essentially Go's MVS. (Can only specify a minimum bound, can't depend across major version bumps). Any others? MVS is more the exception than the rule.
> 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.
I'll bite :-) You lose a lot of expressivity. Incompatibility is specified from the dependee, despite being a property of the dependency. I can point to instances where this has causes issues; e.g. dependees using unstable APIs. That's exactly why MVS uses the _minimum_ bound, to minimise such breaks.
> Building a SAT solver into the package manager seems to be a solution in search of a problem.
I agree in that there are better algorithms for error reporting! But NP-hardness is a pretty fundamental property of dependency resolution and removing it moves the pain somewhere else.
> Building a SAT solver into the package manager seems to be a solution in search of a problem.
I can't tell you which ones off the top of my head, but I'm sure a number of package managers do use constraint solvers to find dependencies matching the constraints.
> I thought Cargo did a simple SemVer check and then imported both if there was a conflict
Not quite, Cargo only allows multiple versions of a package when they are semver incompatible (i.e. have different major versions).
If you allow multiple versions of a package you get some quite gnarly errors if you try to share values between them. The rationale of allowing semver incompatible versions is that they should be incompatible anyway.
Cargo has an interesting proposal on private and public dependencies that allows you to say multiple versions are only allowed when they aren't visible from the same part of the dependency graph https://rust-lang.github.io/rfcs/3516-public-private-depende...
A minor point, but npm peer dependencies mean that in theory it actually is NP-hard! Even if it's rarely exhibited in practice.