this is sad

That's a fairly major 'if'. It's already not too great with tens of thousands of packages[0]; I don't believe it can ever scale another three orders of magnitude (which is what would be required to be truly mainstream) without a change in approach.

If I understand correctly, package managers have already given up on finding 'optimal' solutions[1] and now use heuristic SAT solvers, but regardless, at some point distros have to let go of the idea that the installability of a given package is a function of *every other possible package*. Eventually to continue scaling there simply has to be some demarcation line that lets the solver prune the tree to something small enough to keep dependency resolution tractable. One way to do this is by separation of a core platform from leaf packages that don't (or rarely) have complex interdependencies, which coincidentally happens to describe how almost every end user actually wants a system to work.

[0]in the sense that both apt and aptitude can take a while to find a solution, especially on a less powerful machine, and aptitude will happily suggest a seemingly endless selection of terrible 'solutions'

[1] in the sense of calculating the minimal set of changes required to satisfy the request