まむの備忘録

まむです。備忘録です。

3SATがNP完全であることの証明

以下の問題3SATはNP完全である。証明の概略を示す。 3SAT INPUT: を変数集合とする。の任意の元か、その否定をリテラル(literal)という。幾つかのリテラルの選言をクローズ(clause)という。であるような幾つかのクローズたちの連言が入力である。 OUTPUT: …