Regarding the computational difficulty of dependency resolution, I ran into a pathological case with Bundler a while back [1]. The money quote from the EDOS folk is:
> automatic package installation tools ... live dangerously on the edge of intractability, and must carefully apply heuristics that may be either safe, and hence still not guaranteed to avoid intractability, or unsafe, thus accepting the risk of not always finding a solution when it exists.
In other words, you either risk running into pathological cases (as I did with Bundler) that will come up with a solution only after many hours (or more), or you use methods that terminate quickly but will not find every solution.
> automatic package installation tools ... live dangerously on the edge of intractability, and must carefully apply heuristics that may be either safe, and hence still not guaranteed to avoid intractability, or unsafe, thus accepting the risk of not always finding a solution when it exists.
In other words, you either risk running into pathological cases (as I did with Bundler) that will come up with a solution only after many hours (or more), or you use methods that terminate quickly but will not find every solution.
[1] http://polycrystal.org/2012/03/07/bundler_searches_an_np_com...