You don't need any complex algorithms such as SAT solvers for makefiles, because make does not need to choose from alternative ways to build an out-of-date make

You don't need any complex algorithms such as SAT solvers for makefiles, because make does not need to choose from alternative ways to build an out-of-date makefile dependency. Either the dependency file already has a date newer than all its dependencies, or the file will be rebuilt by following deterministic rules. The reason package dependencies can get complex in Linux distributions is that you can choose different versions of a package, and each version has dependencies on specific version ranges of other packages. Of course it would be a lot easier if you could choose to install multiple versions of the same package in parallel, and don't care about minimising the number of parallel versions.