充足可能性とは？
じゅうそくかのうせい
充足可能性とは、ある論理式を真にする変数の値割り当てが少なくとも1つ存在するかどうかという論理学・計算理論上の概念です。
充足可能性（satisfiability）とは、命題論理や述語論理において、ある論理式（命題式）に対して、それを「真（true）」にするような変数の値の組み合わせが存在するかを問う概念です。存在するならその式は「充足可能（satisfiable）」、いかなる値の組み合わせでも偽になるなら「充足不可能（unsatisfiable）」と呼びます。
命題論理での充足可能性問題（SAT問題）は、与えられた命題式を真にする変数への0または1の割り当てが存在するかを判定する問題です。例えば、変数AとBに対して「(A OR B) AND (NOT A OR B)」という式は、A=偽・B=真のとき真になるため充足可能です。
SAT問題は計算複雑性理論において非常に重要な位置を占めます。
- 1971年にスティーブン・クックによってNP完全問題であることが証明された（クック-レビンの定理）
- NP完全とは「解を検証することは多項式時間でできるが、解を見つけることが困難とされる問題クラス」に属することを意味する
- P≠NP予想（未解決問題）と深く結びついている
現代では高性能なSATソルバーが開発されており、AI・形式検証・コンパイラ最適化・暗号解析などの実用分野で広く活用されています。充足可能性の概念は、コンピュータ科学の理論的基盤を形成する重要な概念のひとつです。
使い方・例文
論理学の授業や情報工学の研究で、「この命題式を満たす変数の組み合わせは存在するか」を問うときに「充足可能性を調べる」と表現します。
この用語をシェア
最終更新: