乱択アルゴリズム紹介(3SATのO(1.334^n)時間アルゴリズム) | Preferred Research

\(\mathcal{C} = (x \vee y \vee z) \wedge (\neg x \vee y \vee z) \wedge (y \vee \neg z \vee w)\). 上の例だと、例えば\(\alpha(x) = \mathrm{true}, \alpha(y) = \mathrm{true}, \alpha(z) = \mathrm{false}, \alpha(w) = \mathrm{false}\)とすれば全ての節を充足することが出来ます。 3SATはNP完全なので全てのNPに属す問題は3SATとして解けるのですが、そうでなくても多くの問題から”自然”に3SATが導出されます。なので3SATを解くアルゴリズムを考えましょう。一番自明なアルゴリズムは次のようになると思います。変数の数を\(n\)、節の数を\(m\)としましょう。

[ymym3412]

[[cs]

[hiromark]

ざーっと読んだけど興味深そう。

[labunix]

乱択アルゴリズム紹介(3SATのO(1.334^n)時間アルゴリズム)