[Onavo]

Very good points. Though to be pedantic, for package managers with concurrent/diamond dependencies support, there's nothing stopping you from pulling in every single dependency of every dependency (this is ~linear time with respect to the depth dependency tree, since you are not conducting any search here but just pulling them in at face value), and maybe deduplicating in linear/constant time with a Set data structure. In this case it's it's very obviously not a SAT problem, but it's ridiculously inefficient since there's zero optimization on the dependency tree. The moment you apply optimizations on it to turn it into a graph from a tree and prune it gets closer to, yes, a SAT problem.

[ryangibb]

> there's nothing stopping you from pulling in every single dependency of every dependency

It depends on the exact system; for example npm's peer dependencies means we can reduce from SAT to npm.

But if there is no such functionality (e.g. just the concurrent package calculus with g(v)=v) they yes, I agree.