充足可能性問題SAT
satisfinability problem
与えられた論理式が充足可能であることを検査する問題
$ \mathrm{SAT}=\{\lang\phi\rang|\phiは充足可能な論理式$ \}
NP完全問題である
NP完全問題の中でも最も重要な問題mrsekut.icon*2
Cook-Levinの定理
参考
充足可能性問題 - Wikipedia
https://www.ci.seikei.ac.jp/yamamoto/sat.html
http://lis2.huie.hokudai.ac.jp/~kurihara/classes/AI/sat.pdf