3SAT問題
3CNF論理式
が
充足可能
かどうかを検査する問題
この問題は
NP完全問題
である
ある問題が
NP完全問題
であることを示すために、
その問題が、3SAT問題に
多項式時間還元
であることをよく使う
充足可能性問題SAT
へ帰着する
https://toshusai.hatenablog.com/entry/2017/12/15/121436
証明 ref
『計算理論の基礎 3』.icon
p.339
充足可能性問題SAT
が3SATに
多項式時間還元
であることを示す
参考
https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#3-satisfiability
https://toshusai.hatenablog.com/entry/2017/12/15/121436