ウィキペディア

関数問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2010/02/01 01:55 UTC 版)

(函数問題 から転送)

関数問題（かんすうもんだい、function problem）とは、各入力に対してある出力を返す形式の問題をいう。計算問題とも呼ばれる。一般に計算理論で問題といった場合関数問題を指し、主に決定問題と対比して用いられることが多い。文字列上の写像で表される。また、決定問題は出力が{0,1}であるような関数問題の部分集合である。