2-SATとは SATとはsatisfiability(充足性)の略で、与えられた論理式を満たす真偽値の組合せが存在することをいう。特に2-SATとは、変数がx_1からx_nまであるとして以下の形の論理式について変数の真偽値の組合せを考える問題である。 ここで 論理積でつながれたひとつひとつの部分(節)に変数が二つある(節の長さが2である)…