\(\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\)としましょう。
![乱択アルゴリズム紹介(3SATのO(1.334^n)時間アルゴリズム) | Preferred Research](https://cdn-ak-scissors.b.st-hatena.com/image/square/92e9d18a95fa6b2a70df179fd38f027e7d66dcd6/height=288;version=1;width=512/https%3A%2F%2Ftech.preferred.jp%2Fwp-content%2Fuploads%2F2019%2F11%2Fogimage.png)