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).

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.

    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 != 1