▲ 4 ▼ Dependency hell is NP-complete
The package version selection problem is to find a set of dependencies that can be used to build a top-level package P that is complete (all dependencies satisfied) and compatible (no two incompatible packages are selected). There may be no such set, because of the diamond dependency problem: perhaps A needs B and C; B needs D version 1, not 2; and C needs D version 2, not 1. In this case, assuming it’s not possible to choose both versions of D, there is no way to build A.
Register to comment or vote on this story
Once upon a time, this was a 'solved problem in computer science', and the solution strength-reduced to O(n log n), somewhat down from NP-complete. Glibc has bits of it in Linux, Solaris depended on it, and it was first thoroughly discussed on Multics. I'll try to do the archeology and write it up in my Copious Spare Time.