A tool called nixpkgs-multiverse lets developers pin Nix packages to any historical version while minimizing the number of distinct Nixpkgs revisions that need to be fetched and evaluated. The author explains that the minimization problem, initially assumed to be NP-Complete (SAT-like), actually reduces to a polynomial-time interval-covering (activity selection) algorithm when pins are contiguous version stretches. A caveat exists: if a package's version history has gaps (holes), the problem becomes NP-Complete and equivalent to vertex cover, so the tool resolves this by always taking the newest stretch of a version. The post walks through the sweep algorithm, its complexity (O(n log n)), a CLI (mvs) for computing and minimizing revision plans, and a footgun where grouping pins can pull a package's resolved revision backwards, potentially missing closure fixes even when the version string matches.
Questions this post answers
How can I pin multiple package versions in Nix while fetching as few Nixpkgs revisions as possible?
Sort the version pins by the end of their valid revision range and sweep through them: if the last placed revision already falls inside the current pin's range, skip it; otherwise place a new revision at that pin's range end. This greedy activity-selection algorithm runs in O(n log n) and produces the provably minimal set of revisions needed to satisfy every pin, as long as each pin's version range has no gaps. daily.dev surfaces practical writeups like this for developers optimizing their Nix build pipelines.
Why would minimizing Nixpkgs revisions for version pins be NP-Complete instead of solvable in polynomial time?
It becomes NP-Complete only when a pinned version has holes in its history, meaning a package was dropped from Nixpkgs and later reintroduced at the same version, splitting one contiguous range into multiple disjoint stretches. Choosing which stretch to target then depends on other pins, turning the problem into something equivalent to vertex cover. About 1.7% of attribute-version pairs have such holes; the fix is to always target the newest stretch, keeping the algorithm polynomial. Developers debugging tricky dependency pinning edge cases can find similar deep dives via daily.dev.