充足可能性問題とは何？わかりやすく解説 Weblio辞書

充足可能性問題

読み方：じゅうそくかのうせいもんだい
【英】：satisfiability problem

真または偽を表す論理変数とそれらの否定からなる和積形論理式, 例えば $(x_1 \lor \bar{x}_2 \lor x_3) \land (\bar{x}_1 \lor \bar{x}_3) \land (x_2 \lor \bar{x}_3)\,$ が与えられているとき, この式が真になるような論理変数への割り当てが存在するとき充足可能といい, それを判定する問題をいう. クック (Cook) が1971年にNP完全性を示した最初の問題. デイビス・プットナム (Davis-Putnam) のアルゴリズムなどが知られている. 以上は命題論理における充足可能性問題であるが, 述語論理における充足可能性問題は決定不能である.

「OR事典」の他の用語

組合せ最適化：

ロバース数一般化割当問題並列アルゴリズム充足可能性問題分散アルゴリズム分枝切除法分枝限定法

ウィキペディア

索引トップ用語の索引ランキングカテゴリー

充足可能性問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/04/13 16:34 UTC 版)

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

[続きの解説]

「充足可能性問題」の続きの解説一覧

>> 「充足可能性問題」を含む用語の索引
充足可能性問題のページへのリンク

充足可能性問題とは？わかりやすく解説

充足可能性問題

充足可能性問題

「充足可能性問題」の関連用語


	Copyright (C) 2024 （社）日本オペレーションズ・リサーチ学会 All rights reserved.
	All text is available under the terms of the GNU Free Documentation License. この記事は、ウィキペディアの充足可能性問題 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

充足可能性問題とは？ わかりやすく解説

充足可能性問題

充足可能性問題

「充足可能性問題」の関連用語

充足可能性問題とは？わかりやすく解説