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?
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.
So the real question is, which assumption does the package of 'Nix-using developer + Nix' give up?
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.
This approach offers a great deal of advantages, including very fast (roughly linear) calculation of what to build, full determinism in what gets built, and the ability to specify any arbitrary nix expression as a dependency, say some C library or a command-line tool, rather than being limited just to specifying packages written for your particular language.
However, of course, it does come with some drawbacks. Among them is the requirement that you often can't simply use nix out-of-the-box to build your code; depending on how developed the nix ecosystem is for a particular language, you might have to figure out for language X how packages are built, tested, installed, and linked together, and write the appropriate abstractions in nix. It also means that you won't automatically pick up later versions of a dependency when you (re)build it, which means you might miss out on updates. However, this latter drawback is arguably a benefit, because by the same token you won't accidentally pull in regressions due to an update in a dependency.