決定問題のソースを表示

'''決定問題'''（けっていもんだい、decision problem）とは、各入力に対して受理か拒絶かのうち片方を出力する形式の問題をいう。'''判定問題'''とも呼ばれる。形式的には、文字列全体の集合<math>\{0, 1\} ^*</math>から<math>\{0, 1\}</math>への写像、あるいは<math>\{0, 1\} ^*</math>の部分集合である。

たとえば、ある[[命題論理|命題論理式]]を充足する真理値割り当てがあるかないか（[[充足可能性問題]]）、与えられた[[自然数]]が[[素数]]か否か（[[素数判定|素数判定問題]]）、といったものがある。これに対し、受理か拒絶かだけでなく真理値割り当てや[[素因数分解]]の結果といったものの出力を要求する問題は[[函数問題]]（function problem）と呼ばれる。

決定問題は、数学的に定式化しやすく、かつ出力に関わる時間を考慮しなくてよいことから、[[計算理論]]でよく使われる。

== 関連項目 ==
*[[計算複雑性理論]]
*[[決定可能性]]

{{DEFAULTSORT:けつていもんたい}}
[[Category:論理学]]
[[Category:計算理論]]
[[Category:数学に関する記事]]