The solver might be deterministic if you take some sufficiently large global state into account, but the process of

    apt install bar

from a users view is not. It can have a different result depending on what is already installed, or even if all other system state is the same it can change with time.

My point is that a package "bar v3.2.1" that depends on "libfoo v1.2.3" needs to be considered a different package than "bar v3.2.1" that depends on "libfoo v1.2.4" or even "libfoo v1.2.3 compiled with -O3 instead of -O2", because the resulting package can behave differently due to the variation.

But as soon as you have that there is no need for install time dependency resolution anymore, since it is all done at build time.