Yum is dead, long live DNF http://dnf.baseurl.org/2015/05/11/yum-is-dead-long-live-dnf/ FedoraのパッケージマネージャがYumからSATベースのDNF (Dandified Yum)というものに変わるそうな。
SATベースにというのは、Eclipseがパッケージの依存関係の解決にSAT/Max-SAT/PBソルバであるSAT4Jを使っているのは有名だし、Debian方面でもapt-pbo http://www.mancoosi.org/papers/ase10.pdf なんてのもあったりしたし、HaskellでもZ3を使おうとしている人がいたり https://github.com/haskell/cabal/issues/1783#issuecomment-40690978 で、まあ順当な方向だろう。ちなみに、自分が簡単なSAT/Max-SAT/PBソルバをHaskellで自作しているのも、もとのもとのモチベーションの１つはcabalの依存関係解決に使いたいというのがあったり（現状では全然そっち方面には進めれていないけれど）。
で、DNFはソルバには何を使っているのかなぁと思ったら、既存ソルバを使っているのではなく、libsolv https://github.com/openSUSE/libsolv として、パッケージ依存関係向けに特化して実装したものを使っているのね。うーん……
あと、DNF という名前は Disjunctive normal form (選言標準形) にかけているのだろうけれど、そういう名前は……
そのうえで、「今インストールされているパッケージは出来るだけそのままで」とか「出来るだけ新しいバージョンに揃えたい」みたいなことも考えると最適化問題になって、Max-SATやPBのような話になります。