News for hackers. Stuff that matters.
Re:Thoughts on “Dependency hell is NP-complete” by skrebbel on Saturday December 17, 2016 @03:30AM (#13199877)
I don't understand this. You're saying that the way the dependencies are written down (with code, not declarations) changes the NP-completeness characteristics of dependency resolution.

I strongly doubt that, just like a search in an unindexed database table is O(N) no matter whether you write it as an SQL query or a for loop.

What assumptions about dependencies does Nix make / weaken that makes resolution linear-time? Any of those 4 Russ Cox lists? Or did Nix come up with some genius insight that shows that there's more than 4 core assumptions in the NP Completeness proof and the 5th one is the one that can be safely dropped?

Re:Thoughts on “Dependency hell is NP-complete” by DougBTX on Saturday December 17, 2016 @04:15AM (#13199965)
> > Whatever that variable resolves to

The "fifth" or perhaps "zeroth" assumption is that the versions of all the dependencies must be resolved by a single system. If the developer does half the work by e.g., defining explicitly what flask is, then the remaining part of the system won't have to be NP complete any more.

I think that's what the parent post means by "won't automatically pick up later versions of a dependency". Since it isn't doing full dependency resolution, it doesn't need to solve the whole problem, but also doesn't give all the benefits.

Re:Thoughts on “Dependency hell is NP-complete” by smallnamespace on Saturday December 17, 2016 @12:51PM (#13201599)
Even though the developer does half the work, the system of 'Nix-using developer + Nix' is still constrained by NP-completeness, so in practice the two combined will not be able to solve the 'dependency resolution problem' in its full generality without a potentially exponential search.

So the real question is, which assumption does the package of 'Nix-using developer + Nix' give up?

Re:Thoughts on “Dependency hell is NP-complete” by cwp on Saturday December 17, 2016 @01:34PM (#13201772)
It violates assumption #4. With nix, you can have multiple versions of a package installed.
Re:Thoughts on “Dependency hell is NP-complete” by Zalastax on Saturday December 17, 2016 @08:19AM (#13200603)
As far as I can tell Nix doesn't do dependency resolution at all [1]. Hard linking every dependency is a solution but is undecireable for most systems. I don't want to specify versions for sub-dependencies so I want them to be automatic and we have the NP-problem again. It might be a smaller set of possibilities if most versions are pinned but it's still NP. [1]: https://medium.com/@charlesstrahan/as-a-nix-nixpkgs-nixos-co...
Re:Thoughts on “Dependency hell is NP-complete” by cwp on Saturday December 17, 2016 @01:04PM (#13201643)
If by "dependency resolution" you mean solving the SAT-equivalent constraint problem the article talks about, then yes, Nix does not do that.

But, it does solve the simpler problem of installing a package along with the all of its transitive dependencies. Nix packages specify the exact version of each package it depends on, so you never have to recursively specify sub-dependencies. Installation is just a matter of walking an acyclic graph. It's not NP complete.

Re:Thoughts on “Dependency hell is NP-complete” by zzzcpan on Saturday December 17, 2016 @01:35PM (#13201781)
Actually, his 4th assumption is somewhat broken. A package manager that does automatic upgrades can choose to upgrade all affected packages as a some sort of transaction always keeping a single version and all dependencies resolved without an NP problem.