Version SAT とは

via reddit /r/haskell

research!rsc: Version SAT

以下の条件を課すとパッケージ管理はNP完全問題。従って多くのパッケージマネージャーはSATソルバーを必要とする。

1. A package can list zero or more packages or specific package versions as dependencies.
2. To install a package, all its dependencies must be installed.
3. Each version of a package can have different dependencies.
4. Two different versions of a package cannot be installed simultaneously.

実際、多くのマネージャーがSATソルバーを使っている。Linux distributionだけでなくある言語のライブラリを選ぶ場合も全く同じことなのでこういうマネージャーは10を超えている。もちろん条件を変えればNP完全問題ではなくなる。例えば1とか4を緩和する。

だったらパッケージマネージャーがSAT問題を解けるだろうと考えた人がいて、dpkgでsudokuを解くとか。