3SATがNP完全であることの証明
以下の問題3SATはNP完全である。証明の概略を示す。
3SAT
INPUT:
を変数集合とする。の任意の元か、その否定をリテラル(literal)という。幾つかのリテラルの選言をクローズ(clause)という。であるような幾つかのクローズたちの連言が入力である。
OUTPUT:
が充足可能かどうか判定する。すなわち、を真にするような各変数への真偽割り当てが存在するか判定する。
NP完全性の証明の流れ
ある判定問題が、NP完全であることを示したいときは以下の二つを示せばよい。
・であること。
・あるNP完全である問題が存在して、の任意のインスタンスがのインスタンスに多項式時間で変形でき、が成り立つ。(多項式時間多対一帰着という)
3SATのNP完全性証明
3SATがNPに属することを簡単に述べておく。 3SATの入力とその真偽割り当てが与えられたら、その割り当てが入力の論理式を充足するかを多項式時間で判定できるので3SATはNPに属する。 後者の帰着証明には、Cookの定理を用いる。 すなわち、SATがNP完全であることを用いる。 SATのインスタンス から3SATのインスタンスを構成し、が充足可能であるときにのみが充足可能であることを示せばよい。 各がいくつのリテラルから成っているかで場合に分ける。
(1) のとき
新しい変数を導入して、とする。
(2) のとき
新しい変数を導入して、とする。
(3) のとき
とする。
(4) のとき
新しい変数を導入して、とする。
以上のように構成したの選言をとする。との充足可能性が同値であることは後者の構成から明らか。