充足可能性問題 SAT と 3SAT

命題変数 $x_1, \ldots, x_n$ に対し、$x_i$ または $\lnot x_i$ の形の式をリテラル、リテラルの論理和 $(\ell_1 \lor \cdots \lor \ell_k)$ を節、節の論理積 $C_1 \land \cdots \land C_m$ を CNF 論理式（連言標準形）といいます。真理値割当 $\alpha : \{x_1,\ldots,x_n\} \to \{\text{真}, \text{偽}\}$ が CNF 論理式 $\varphi$ を真にするとき、$\alpha$ は $\varphi$ を充足するといい、そのような $\alpha$ が存在する $\varphi$ を充足可能といいます。

とおきます。さらに、すべての節がちょうど 3 個のリテラルからなる CNF 論理式に制限したものを $\mathrm{3SAT}$ と書きます。