Dependency resolution with versions is indeed NP-hard, if versions "conflict" (2 versions of the same package can't be installed at the same time). What if they don't conflict, and you just wanna install the fewest possible package versions to satisfy all dependencies? That's NP-hard too.