充足可能性問題
充足可能性問題は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完全問題である。
論理式全体の値を真にするような、真偽値 x 1 , x 2 ... {\displaystyle x_{1},x_{2}\dots } の組み合わせは存在するか?