充足可能性問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』

充足可能性問題（じゅうそくかのうせいもんだい、satisfiability problem, SAT）は、
一つの乗法標準形 (CNF) が与えられたとき、それに含まれるすべての変数の値を
偽(False)あるいは真(True)にうまく定めることによって全体の値を'真'にできるか、という問題をいう。

目次 1 定義 2 例題 3 NP完全 4 関連項目

[編集] 定義

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

• 論理否定 が真ならば偽 偽ならば真
• 論理和 が真ならば 偽ならば
• 論理積 が真ならば 偽ならば

• リテラル -- 論理変数 またはその否定
• クロージャ -- リテラルの論理和

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

[編集] 例題

• 

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

• 

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

[編集] NP完全

充足可能性問題はNPかつNP困難な問題である。このような問題のクラスをNP完全問題という。
充足可能性問題を多項式時間で変形することによって、様々なNP完全問題を構成することができる。

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

• CNF-SAT -- クロージャの論理積からなるもの。
• 3-SAT -- CNF-SATのうち、クロージャ内のリテラル数が、高々3つのもの。

[編集] 関連項目

• 数理論理学
• NP完全問題