Figuring out how it works is a great way to learn a bit more about how Python packaging works under the hood. I learned that .whl files contain a METADATA file listing dependency constraints as "Requires-Dist" rules.
I ran a speed comparison too. Using the uv pip resolver it took 0.24s - with the older pip-compile tool it took 17s.
Which is one of the reasons why uv is so fast. It reduces the total times it needs to go to PyPI! Not only does it cache really well, it also hits PyPI more efficiently and highly parallel. Once you resolved once, future resolutions will likely bypass PyPI for the most part entirely.
Of course we could've cached the venv, but cache invalidation is hard, and this is a very cheap way to avoid it.
The reason uv is fast is that it creates hard links from each of your virtual environments to a single shared cached copy of the dependencies (using copy-on-write in case you want to edit them).
This means that if you have 100 projects on your machine that all use PyTorch you still only have one copy of PyTorch!
Is that actually sufficient? Can every system that’s solving something that’s NP-complete solve every other NP-complete problem?
Others have given the answer (yes) and provided some links. But it is nice to have an explanation in thread so I'll have a go at it.
The key idea is the idea of transforming one problem to another. Suppose you have some problem X that you do not know how to solve, and you've got some other problem Y that you do know how to solve.
If you can find some transform that you can apply to instances of X that turns them into instances of Y and that can transform solutions of those instances of Y back to solutions of X, then you've got an X solver. It will be slower than your Y solver because of the work to transform the problem and the solution.
Now let's limit ourselves to problems in NP. This includes problems in P which is a subset of NP. (Whether or not it is a proper subset is the famous P=NP open problem).
If X and Y are in NP and you can find a polynomial time transformation that turns X into Y then in a sense we can say that X cannot be harder than Y, because if you know how to solve Y then with that transformation you also know how to solve X albeit slower because of the polynomial time transformations.
In 1971 Stephen Cook proved that a particular NP problem, boolean satisfiability, could serve as problem Y for every other problem X in NP. In a sense then no other NP problem can be harder than boolean satisfiability.
Later other problems were also found that were universal Y problems, and the set of them was called NP-complete.
So if Python packaging is NP-complete then every other NP problem can be turned into an equivalent Python packaging problem. Note that the other problem does not have to also be NP-complete. It just has to be in NP.
Sudoku and Python Packaging both being NP-complete means it goes both ways. You can use a Python package solver to solve your sudoku problems and you can use a sudoku solver to solve your Python packaging problems.
Yes, by definition (https://en.wikipedia.org/wiki/NP-completeness , point 4).
The problem class of "Solve an arbitrary Sudoku of Size 9" might even be constant runtime, since it's a finite set to search through.
This video I think makes it obvious why that's true in a pretty intuitive way. I posted it a few days ago as a link and it never got traction.
SAT is the equivalent of being able to find the inverse of _any_ function, because you can describe any function with logic gates (for obvious reasons), and any collection of logic gates that describes a function is equivalent to a SAT problem. All you need to do is codify the function in logic gates, including the output you want, and the ask a SAT solver to find the inputs that produce that output.
Now it is just an exhaustive, recursive search: for the current package try using versions from newest to oldest, enqueue its dependencies, if satisfied return, if conflict continue.
https://web.archive.org/web/20160326062818/http://algebraict...
Requires-Dist: sudoku_0_1 != 1
Requires-Dist: sudoku_0_2 != 1
Requires-Dist: sudoku_0_3 != 1
Requires-Dist: sudoku_0_4 != 1
Requires-Dist: sudoku_0_5 != 1
Requires-Dist: sudoku_0_6 != 1
Requires-Dist: sudoku_0_7 != 1
Requires-Dist: sudoku_0_8 != 1
Requires-Dist: sudoku_1_0 != 1
Requires-Dist: sudoku_2_0 != 1
Requires-Dist: sudoku_3_0 != 1
Requires-Dist: sudoku_4_0 != 1
Requires-Dist: sudoku_5_0 != 1
Requires-Dist: sudoku_6_0 != 1
Requires-Dist: sudoku_7_0 != 1
Requires-Dist: sudoku_8_0 != 1
Requires-Dist: sudoku_0_1 != 1
Requires-Dist: sudoku_0_2 != 1
Requires-Dist: sudoku_1_0 != 1
Requires-Dist: sudoku_1_1 != 1
Requires-Dist: sudoku_1_2 != 1
Requires-Dist: sudoku_2_0 != 1
Requires-Dist: sudoku_2_1 != 1
Requires-Dist: sudoku_2_2 != 1https://github.com/konstin/sudoku-in-python-packaging/blob/m...