決定問題（けっていもんだい、decision problem）とは、入力に対してYesまたはNoで出力する形式の問題のことであり、判定問題とも呼ばれる。たとえば、ある論理式を充足する真理値割り当てがあるかないか（論理式充足可能性問題）、与えられた自然数nが合成数か素数か（素数判定問題、PRIMES）、といったものがある。これに対し、Yes,Noだけでなく上で言えば真理値割り当てや素因数分解の結果といったものの出力を要求する問題は関数問題(function problem)と呼ばれる。

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

関連項目

• 計算複雑性理論
• P
• NP

論理学 | 数学基礎論

Entscheidungsproblem | Decision problem | Problème de la décision