充足可能性問題のアルゴリズム

充足可能性問題（satisfiability problem）とは？ 充足可能性問題（以下，ＳＡＴ問題と略す）とは， 理論計算機科学で最も基本的で 重要な ＮＰ完全問題 の一つである． グラフ理論における 巡回セールスマン問題，頂点彩色問題，独立頂点集合問題， オペレーションズ・リサーチにおける整数計画問題， ゲーム・パズルにおける数独，テトリスなど， 実社会で遭遇する多くの（決定）問題がＮＰ完全問題である． その中でも， ＳＡＴ問題は，そのＮＰ完全性が示された最初の問題である． 以下の意味で， ＳＡＴ問題は，ＮＰ完全問題の根本である： すべてのＮＰ完全問題のＮＰ完全性は， （いくつかの例外を除いて） ＳＡＴ問題からの有限回の多項式時間還元を経て示された． 例えば， 教科書 [1] では， ハミルトン閉路問題は， 頂点被覆問題からの多項式時間還元により， 更に， 頂点被覆問題はＳＡＴ問題か

[rjj]

「Bela Bollobas（ランダムグラフ） や Paul Vitanyi（コルモゴロフ計算量）といったその分野の権威が， 大胆にも P=NP と予想したことも興味深い」