5 ms·
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
by skrebbel 10y ago
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?
- DougBTX 10y ago> > 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.
- smallnamespace 10y agoEven 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?
- cwp 10y agoIt violates assumption #4. With nix, you can have multiple versions of a package installed.
- Zalastax 10y agoAs 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-contributor-i-figured-id-clear-up-a-few-things-947f8583217e https://medium.com/@charlesstrahan/as-a-nix-nixpkgs-nixos-co...
- cwp 10y agoIf 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.
- zzzcpan 10y agoActually, 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.