判定問題

ウィキペディア

決定問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/08/19 15:39 UTC 版)

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