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.