関数問題

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

関数問題の主なクラス

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に含まれるより具体的な問題のクラス。

主な関数問題

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

関数問題の主なクラス

主な関数問題

関連項目