「決定問題」の版間の差分

削除された内容 追加された内容
編集の要約なし
Sergei 1207 (会話 | 投稿記録)
m 174.142.192.26 (会話) による版を Melan による版へ巻き戻し
1行目:
'''決定問題'''(けっていもんだい、decision problem)とは、各入力に対して受理か拒絶かのうち片方を出力する形式の問題をいう。'''判定問題'''とも呼ばれる。形式的には、文字列全体の集合<math>\{0, 1\} ^*</math>から<math>\{0, 1\}</math>への写像、あるいは<math>\{0, 1\} ^*</math>の部分集合である。
 
たとえば、ある[[命題論理|命題論理式]]を充足する真理値割り当てがあるかないか([[充足可能性問題]])、与えられた[[自然数]]が[[素数]]か否か([[素数判定|素数判定問題]])、といったものがある。これに対し、受理か拒絶かだけでなく真理値割り当てや[[素因数分解]]の結果といったものの出力を要求する問題は[[数問題]](function problem)と呼ばれる。
 
決定問題は、数学的に定式化しやすく、かつ出力に関わる時間を考慮しなくてよいことから、[[計算理論]]でよく使われる。