関数問題のソースを表示

'''関数問題'''（かんすうもんだい、function problem）とは、[[計算量理論]]において、各入力に対してある出力を返す形式の問題をいう。'''評価問題'''とも呼ばれる。文字列上の写像<math>\Sigma ^* \to \Sigma ^*</math>で表される。主に[[判定問題]]（関数問題のうち出力が<math>\{0, 1\}</math>であるようなもの）と対比して用いられることが多い。

== 関数問題の主なクラス ==
; FP (Function P, P Search Problem)
: 決定性[[チューリングマシン]]により多項式時間で解かれる関数問題のクラス。
; FNP (Function NP, NP Search Problem)
: 非決定性チューリングマシンにより多項式時間で解かれる関数問題のクラス。
; TFP (Total FP)
: FPに属するもののうち必ず解が存在するような問題のクラス。
; TFNP (Total FNP)
: FNPに属するもののうち必ず解が存在するような問題のクラス。
; PLS (Polynomial Local Search)
; PPP (Polynomial Pigeonhole Principle)
; PPA (Polynomial Parity Argument)
; PPAD (Polynomial Parity Argument with Directed graph)
: PLS以下、TFNPに含まれるより具体的な問題のクラス。

== 主な関数問題 ==
; 充足割り当て問題
: 決定問題である[[充足可能性問題]]と対比してこう書かれる。
; [[最大クリーク問題]]
; [[巡回セールスマン問題]]

== 関連項目 ==
*[[計算複雑性理論]]
*[[最適化問題]]

{{DEFAULTSORT:かんすうもんたい}}
[[Category:計算複雑性理論]]
[[Category:数学の問題]]
[[Category:数学に関する記事]]