The description you've given for apt just sounds almost exactly like SAT, a problem that's very efficiently approximated. That's exactly how the --solver 3.0 flag on recent apt versions works [0].

[0] https://blog.jak-linux.org/2024/05/14/solver3/