Possibly related: http://wiki.apidesign.org/wiki/LibraryWithoutImplicitExportI.... This one seems to avoid the NP-completeness by giving up when it encounters a conflict between major versions of the same package. (instead of trying to figure out whether it could modify the solution to avoid the conflict by upgrading/downgrading some packages).
In the context of language package managers avoiding NP-completeness is interesting: if you have a global repository then you have to deal with conflicts in some way, however per-project repositories could try to get around limitation #4 (2 different versions of same package allowed to be installed). Whether it is desirable to do so is another matter though, you'd end up with various buggy versions of same package installed, never knowing whether you've fully upgraded to the fixed version...
Treating different major versions as different packages is interesting though, and happens to some extent in system packages already (e.g. both python2 and python3 can coexist)
In the context of language package managers avoiding NP-completeness is interesting: if you have a global repository then you have to deal with conflicts in some way, however per-project repositories could try to get around limitation #4 (2 different versions of same package allowed to be installed). Whether it is desirable to do so is another matter though, you'd end up with various buggy versions of same package installed, never knowing whether you've fully upgraded to the fixed version...
Treating different major versions as different packages is interesting though, and happens to some extent in system packages already (e.g. both python2 and python3 can coexist)