2005年6月1日 (水) 16:43時点における版編集小太刀 (会話 \| 投稿記録) 8,187 回編集 m →‎関連項目 ← 古い編集		2005年8月9日 (火) 03:21時点における版編集取り消し Riesz (会話 \| 投稿記録) 374 回編集スタイル、追記新しい編集 →
1行目: '''決定問題'''（~~'''~~けっていもんだい~~'''）~~、decision problem）とは、入力に対してYesまたはNoで出力する形式の問題のことであり、判定問題とも呼ばれる。このたとえば、ある[[論理式]]を充足する真理値割り当てがあるかないか（論理式充足可能性問題の解）、与えられた[[自然数]]''n''が[[合成数]]か[[素数]]か（素数判定問題、PRIMES）、といったものがある。これに対し、Yes,Noだけできなく上で言えば真理値割り当てもよや素因数分解の結果といったものの出力を要求する問題は[[関数問題]](function problem)と呼ばれる。 ~~;決定問題の例:与えられた自然数nは素因数分解可能かどうか~~ 決定問題は、数学的に定式化しやすく、かつ出力に関わる時間を考慮しなくてよいことから、[[計算理論]]の世界でよく使われる。 === 関連項目= == [[計算複雑性理論]] [[P]] *[[NP]]

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