充足可能性問題

充足可能性問題（じゅうそくかのうせいもんだい、satisfiability problem, SAT）は、一つの命題論理式が与えられたとき、それに含まれる変数の値を偽 (False) あるいは真 (True) にうまく定めることによって全体の値を'真'にできるか、という問題をいう。SATisfiabilityの頭3文字を取ってしばしば「SAT」と呼ばれる。

定義

真偽値をとる論理変数 $\textstyle {x_{1},x_{2}\dots }$ および論理演算子により論理式を構成する。

• 論理否定 $({\bar {x_{1}}})\dots x_{1}$ が真ならば偽 偽ならば真
• 論理和 $(x_{1}\lor x_{2})\dots x_{1}$ が真ならば $x_{1}\,$ 偽ならば $x_{2}\,$
• 論理積 $(x_{1}\land x_{2})\dots x_{1}$ が真ならば $x_{2}\,$ 偽ならば$x_{1}\,$
• リテラル - 論理変数 $(x_{1})\,$ またはその否定 $({\bar {x_{1}}})$
• 節 - リテラルの論理和 $(x_{1}\lor {\bar {x_{2}}}\lor ...)$

問題

論理式全体の値を真にするような、真偽値 $x_{1},x_{2}\dots$ の組み合わせは存在するか？

例題

• $(x_{1}\lor x_{2})\land (x_{1}\lor {\bar {x_{2}}})\land ({\bar {x_{1}}}\lor {\bar {x_{2}}})$

x₁=真, x₂=偽, を代入すると論理式は真になる。よって解答はYes。

• $(x_{1}\lor x_{2})\land ({\bar {x_{1}}}\lor x_{2})\land (x_{1}\lor {\bar {x_{2}}})\land ({\bar {x_{1}}}\lor {\bar {x_{2}}})$

x₁, x₂, いかなる真偽値を代入しても論理式は偽になる。よって解答はNo。

NP完全

充足可能性問題はNP（Non-deterministic Polynomial time（非決定性多項式時間）非決定性チューリングマシンによって多項式時間で解くことができる問題）かつNP困難な問題である。このような問題のクラスをNP完全問題という。充足可能性問題を多項式時間で変形することによって、様々なNP完全問題を構成することができる。

任意の論理式からなる充足可能性問題はNP完全であるが、ある特殊な形状をもつ論理式のクラスに限定しても、なおNP完全であることが証明されている。

• CNF-SAT - 節の論理積からなるもの。

• 3-SAT - CNF-SATのうち、節内のリテラル数が、高々3つのもの。

NP問題の補問題、つまり結果のYesとNoを逆転させた問題をco-NP問題という。

充足可能性問題のYesとNoを逆転させ、論理式に否定をかけて変形すると、トートロジー判定問題になる。トートロジー判定問題はco-NP完全問題である。

関連項目

• 数理論理学
• NP完全問題
• 制約充足問題
• デービス・パトナムのアルゴリズム
• DPLLアルゴリズム
• タブローの方法