「充足可能性問題」の版間の差分
ナビゲーションに移動
検索に移動
細 ("充足可能性問題" を保護しました。 [edit=sysop:move=sysop]) |
Albeit-Kun (トーク | 投稿記録) |
||
| 2行目: | 2行目: | ||
真または偽を表す論理変数とそれらの否定からなる和積形論理式, 例えば<math>(x_1 \lor \bar{x}_2 \lor x_3) \land (\bar{x}_1 \lor \bar{x}_3) \land (x_2 \lor \bar{x}_3)\,</math>が与えられているとき, この式が真になるような論理変数への割り当てが存在するとき充足可能といい, それを判定する問題をいう. クック (Cook) が1971年にNP完全性を示した最初の問題. デイビス・プットナム (Davis-Putnam) のアルゴリズムなどが知られている. 以上は命題論理における充足可能性問題であるが, 述語論理における充足可能性問題は決定不能である. | 真または偽を表す論理変数とそれらの否定からなる和積形論理式, 例えば<math>(x_1 \lor \bar{x}_2 \lor x_3) \land (\bar{x}_1 \lor \bar{x}_3) \land (x_2 \lor \bar{x}_3)\,</math>が与えられているとき, この式が真になるような論理変数への割り当てが存在するとき充足可能といい, それを判定する問題をいう. クック (Cook) が1971年にNP完全性を示した最初の問題. デイビス・プットナム (Davis-Putnam) のアルゴリズムなどが知られている. 以上は命題論理における充足可能性問題であるが, 述語論理における充足可能性問題は決定不能である. | ||
| + | |||
| + | [[Category:組合せ最適化|じゅうそくかのうせいもんだい]] | ||
2008年11月9日 (日) 18:39時点における最新版
【じゅうそくかのうせいもんだい (satisfiability problem)】
真または偽を表す論理変数とそれらの否定からなる和積形論理式, 例えばが与えられているとき, この式が真になるような論理変数への割り当てが存在するとき充足可能といい, それを判定する問題をいう. クック (Cook) が1971年にNP完全性を示した最初の問題. デイビス・プットナム (Davis-Putnam) のアルゴリズムなどが知られている. 以上は命題論理における充足可能性問題であるが, 述語論理における充足可能性問題は決定不能である.
