関数問題
関数問題（かんすうもんだい、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に含まれるより具体的な問題のクラス。
主な関数問題
[編集]- 充足割り当て問題
- 決定問題である充足可能性問題と対比してこう書かれる。
- 最大クリーク問題
- 巡回セールスマン問題