>For (1) and (2), the worst-case just doesn't occur. I mean, installing packages and type checking can surely be slow. But, at least in my career, I've never seen a galactic blow-up.

NP-hard problems are hard to solve exactly, but it's usually possible to get a pretty good approximate solution efficiently. But some search problems are just very hard, even approximately. If you've held an old Debian install through major upgrades with aptitude, you'll have had to see it get lost deep in outer search space pretty regularly.

Sometimes aptitude needs to downgrade a package, uninstall a package, or not install a recommended package to arrive at the right solution. There are many possible packages it could try to downgrade, and each of these creates a brand new mess with new possibilities. This is not something you get with other package managers, and its search strategy is genuinely intractable if you don't help it along by trying to manually figure out the small set of packages that create all the difficulty.