Not very the parts that make it NP hard are allowing libraries to specify maximum versions (and other more complex version ranges). Most of the time libraries use minimum constraints (~) or (^) which allows the heuristic to work like go's algorithm. For rust, node, and other languages libraries can be imported twice as different versions (without requiring a major version renaming like go) this also allows the heuristic to have an out: if it reaches a really complex case it can just give you both versions. Beyond that package management is a barely disguised 3-SAT solver which we have good, fast solvers. There are definitely some edge cases, but when's the last time you ran any of the following package managers and worried about dependency solve speed? cargo, apt-get, npm (and yarn), dnf, zypper. IO far and away dominates the profiles of these programs, solver speed is basically a non-issue in practice.

depends on the complexity. if it is 2^1000 then forget about finding an optimal result.