充足可能性とは？

じゅうそくかのうせい

ある論理式を真にするような変数への真偽割り当てが少なくとも一つ存在するかどうかを問う性質です。

充足可能性（satisfiability）とは、論理式 φ に対してそれを真にするような命題変数への割り当て（解釈）が少なくとも一つ存在するかどうかという性質のことである。充足不能（unsatisfiable）とはいかなる割り当てでも偽となること、恒真式はすべての割り当てで真となる充足可能式である。充足可能性判定問題（SAT）は計算複雑性理論で NP 完全問題の代表例として知られる。