充足可能性問題
出典: フリー百科事典『ウィキペディア(Wikipedia)』
充足可能性問題(じゅうそくかのうせいもんだい、satisfiability problem, SAT)は、一つの論理積系 (CNF) が与えられたとき、
それに含まれるすべての変数の値を0(偽)あるいは1(真)にうまく定めることによって全体の値を1(真)にできるか、という問題という。
[編集] 定義
0(偽)あるいは1(真)を値にとる変数をX1, X2, ...とする。
論理演算子を以下のものとする。
- 論理否定 (¬X1) -- X1 が真ならば偽、偽ならば真
- 論理和 (X1∨X2) -- X1, X2 のどちらかが真であれば真
- 論理積 (X1∧X2) -- X1, X2 のどちらもが真であれば真
これらの変数と演算子を組合せた論理式を与式とする。
充足可能性問題:変数X1, X2, ...に適当な値(真あるいは偽)を与えたとき、与式全体の値を真にできるか?
[編集] 例題
例1 (P ∨ Q ∨ R) ∧ (¬P ∨ Q ∨ ¬R) ∧ (P ∨ ¬Q ∨ S) ∧ (¬P ∨ ¬R ∨ ¬S)
- P=真, Q=真, R=偽, S=偽, を代入すると与式の値は真になる。
例2 (P ∨ Q) ∧ (¬P ∨ Q) ∧ (P ∨ ¬Q) ∧ (¬P ∨ ¬Q)
- P, Q, いずれの代入値をとっても与式の値は偽になる。
任意の論理式からなる充足可能性問題はNP完全であるが、
ある特殊な形状をもつ論理式だけに限定しても、なおNP完全であることが知られている。
- CNF-SAT -- 変数、またはその否定を論理和でつなぎ、括弧でくくった式をさらに論理積でつないだもの。
- 3-SAT -- CNF-SATのうち、各々の括弧に含まれる変数が、高々3つしかないもの。
カテゴリ: 数学基礎論 | 数学関連のスタブ項目