News for hackers. Stuff that matters.
Re:Thoughts on “Dependency hell is NP-complete” by jpollock on Saturday December 17, 2016 @11:07AM (#13201149)
I didn't understand why it would be NP-complete, dependencies represent an acyclic graph.

However, this is the killer:

"Two different versions of a package cannot be installed simultaneously."

Get rid of that, and your problems disappear.

Which is why my linux server has:

1 gcc-4.8-base:amd64

2 gcc-4.9-base:amd64

3 gcc-5-base:amd64

4 gcc-6-base:amd64

Re:Thoughts on “Dependency hell is NP-complete” by lazyjones on Saturday December 17, 2016 @12:21PM (#13201458)
> dependencies represent an acyclic graph

AFAICT that's not always true. Several scripting languages allow circular dependencies (Node.js, Perl) and so do some popular package managers (with specific workarounds, but the point is that such dependency constellations exist): https://www.debian.org/doc/debian-policy/ch-relationships.ht...

Perhaps the problem needs to be examined differently depending on allowed/existing-in-the-wild circular dependencies.

Re:Thoughts on “Dependency hell is NP-complete” by dozzie on Saturday December 17, 2016 @08:09PM (#13203770)
>> dependencies represent an acyclic graph

> AFAICT that's not always true.

And you are right. apt-get has "upgrade" and "dist-upgrade" commands for a long, long time for a reason (the latter allows to upgrade packages in the presence of dependency cycles and some other cases that would be nasty if left in the middle of upgrade; obviously, no changes that need dist-upgrade land in Debian stable).

Re:Thoughts on “Dependency hell is NP-complete” by amelius on Saturday December 17, 2016 @11:36AM (#13201265)
> "Two different versions of a package cannot be installed simultaneously."

It seems that the problem then might not even have a solution in all cases. So perhaps we should rethink the problem.

Re:Thoughts on “Dependency hell is NP-complete” by Dylan16807 on Saturday December 17, 2016 @01:32PM (#13201761)
It's easy to turn an acyclic graph into a bunch of directories, or to turn a cyclic graph into a bunch of directories and symlinks.

If you allow side-by-side versions then the only remaining failure case is a dependency that doesn't exist.

Nothing to rethink there.