Add to that most package authors putting about a second's thought into their version constraints, with other package authors being overzealous and for example thinking it's their duty to protect you from security vulnerabilities through their version constraints, and I frequently doubt the worth of putting all this SAT wizardry into these tools, as fun as it is.
https://www.anaconda.com/blog/understanding-and-improving-co...
https://docs.astral.sh/uv/reference/resolver-internals/#reso...
This is the reason Conda exist. It is a proper dependency system with all the dependencies recorded in a package's metadata. So it is possible for the package manager to query and know which dependencies a package needs and what the current environment is and then find a set of packages to install.
It's a good thing, however, that using conda doesn't preclude one from also using pip.
The original Conda solver is just badly optimized, whether through the implementation or a poor language choice. For years, user performance concerns were written off as just the price you pay for the correctness of an SAT.
Mamba was a third party rewrite that was a couple orders of magnitude faster. Users started leaving Conda for Mamba. It scared the Conda developer enough that they dropped whatever invisible back-end features they were prioritizing, and within months they added a feature to install different dependency resolution libraries, targeting Mamba first.
Google claims the average number of dependencies is 35. My gut is most of these do not have too many versions, all told. Is this really big enough that you'd expect it to be the bottleneck?