与えられた論理式が充足可能であることを検査する問題

\mathrm{SAT}=\{\lang\phi\rang|\phiは充足可能な論理式\}

NP完全問題である

NP完全問題の中でも最も重要な問題

参考