メインメニューを開く

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

定義編集

真偽値をとる論理変数   および論理演算子により論理式を構成する。

  • 論理否定   が真ならば偽 偽ならば真
  • 論理和   が真ならば   偽ならば  
  • 論理積   が真ならば   偽ならば 
  • リテラル - 論理変数   またはその否定  
  • 節 - リテラルの論理和  

問題編集

論理式全体の値を真にするような、真偽値   の組み合わせは存在するか?

例題編集

  •  
x1=真, x2=偽, を代入すると論理式は真になる。よって解答はYes。
  •  
x1, x2, いかなる真偽値を代入しても論理式は偽になる。よって解答は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完全問題である。

関連項目編集