充足可能性問題 - Wikipedia

英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。 翻訳後、{{翻訳告知|en|Boolean satisfiability problem|…}}をノートに追加することもできます。 Wikipedia:翻訳のガイドラインに、より詳細な

[yuya_presto]

TypeScriptのissueに書いてたNP完全な問題 https://github.com/microsoft/TypeScript/issues/30869

[kiyo_hiko]

「一つの命題論理式が与えられたとき、それに含まれる変数の値を偽 (False) あるいは真 (True) にうまく定めることによって全体の値を'真'にできるか、という問題」

[shiumachi]

"一つの乗法標準形 (CNF) が与えられたとき、それに含まれるすべての変数の値を偽 (False) あるいは真 (True) にうまく定めることによって全体の値を'真'にできるか、という問題"NP完全らしい

[agw]

Satisfiability Problem / SAT

[uechoco]

乗法標準形、充足可能性問題、satisfiability problem、SAT