決定問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/08/19 15:39 UTC 版)
 | この記事は英語版の対応するページを翻訳することにより充実させることができます。（2024年8月） 翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。
|
決定問題（けっていもんだい、decision problem）とは、各入力に対して受理か拒絶かのうち片方を出力する形式の問題をいう。判定問題とも呼ばれる。形式的には、文字列全体の集合
決定問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/01 16:46 UTC 版)
停止問題 - NP困難だがNPではない決定問題。なぜなら、停止問題は決定不可能という問題クラスに属しており、決定不可能はNPより困難で、かつ決定不可能とNPは互いに素だからである。具体的に示すには、NP困難であることは、例えば充足可能性問題を停止問題に容易に還元できることから言える（充足できる解を見付けたら停止し、そうでない場合は無限ループするようなチューリングマシンの停止問題を考えればよい）。NPでないことは、NPに属する問題は全て有限の手続きで決定可能だが、停止問題は一般には決定不可能であることによる。ただし、NP困難でありかつNP完全でない問題の全てが決定不可能というわけではない。例えばTQBF問題(en)はPSPACEで決定可能だが、多分NPではない。 ハミルトン閉路問題 - 巡回セールスマン問題の特殊ケース。NP困難かつNP完全な決定問題。 部分和問題 - ナップサック問題の特殊ケース。NP困難かつNP完全な決定問題。
※この「決定問題」の解説は、「NP困難」の解説の一部です。
「決定問題」を含む「NP困難」の記事については、「NP困難」の概要を参照ください。
ウィキペディア小見出し辞書の「決定問題」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 決定問題のページへのリンク
