関数問題
(函数問題 から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2014/08/22 21:35 UTC 版)
関数問題（かんすうもんだい、function problem）とは、計算量理論において、各入力に対してある出力を返す形式の問題をいう。評価問題とも呼ばれる。文字列上の写像
で表される。主に判定問題（関数問題のうち出力が
であるようなもの）と対比して用いられることが多い。
関数問題の主なクラス
- 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に含まれるより具体的な問題のクラス。
主な関数問題
- 充足割り当て問題
- 決定問題である充足可能性問題と対比してこう書かれる。
- 最大クリーク問題
- 巡回セールスマン問題
関連項目
- 関数問題のページへのリンク
