出典: フリー百科事典『ウィキペディア(Wikipedia)』
| この記事は 英語版の対応するページを翻訳することにより充実させることができます。(2024年4月)翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。
- 英語版記事を日本語へ機械翻訳したバージョン(Google翻訳)。
- 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。
- 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。
- 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。
- 翻訳後、
{{翻訳告知|en|Boolean satisfiability problem|…}} をノートに追加することもできます。
- Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針についての説明があります。
|
| この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。(このテンプレートの使い方) 出典検索?: "充足可能性問題" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL(2023年11月) |
充足可能性問題(じゅうそくかのうせいもんだい、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完全であることが証明されている。
- 3-SAT - CNF-SATのうち、節内のリテラル数が、高々3つのもの。
NP問題の補問題、つまり結果のYesとNoを逆転させた問題をco-NP問題という。
充足可能性問題のYesとNoを逆転させ、論理式に否定をかけて変形すると、トートロジー判定問題になる。トートロジー判定問題はco-NP完全問題である。
論理式の範囲を述語論理式に拡大した場合、ゲーデルの不完全性定理により、充足可能性問題は決定不能である。
平たくいえば、もし述語論理の充足可能性問題が決定可能であるならば、その方法を利用して自然数論によるそれ自身の無矛盾性証明が可能となるが、それは不完全性定理により否定されるからである。
関連項目[編集]