3CNF論理式が充足可能かどうかを検査する問題

この問題はNP完全問題である

ある問題がNP完全問題であることを示すために、

その問題が、3SAT問題に多項式時間還元であることをよく使う

充足可能性問題SATへ帰着する

証明 ref p.339

充足可能性問題SATが3SATに多項式時間還元であることを示す

参考