関数問題（かんすうもんだい、function problem）とは、計算量理論において、各入力に対してある出力を返す形式の問題をいう。評価問題とも呼ばれる。文字列上の写像 Σ ∗ → Σ ∗ {\displaystyle \Sigma ^{*}\to \Sigma ^{*}} で表される。主に判定問題（関数問題のうち出力が { 0 , 1 } {\displaystyle \{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に含まれるより具体的な問題のクラス。
主な関数問題
充足割り当て問題
決定問題である充足可能性問題と対比してこう書かれる。
最大クリーク問題

巡回セールスマン問題

関連項目

計算複雑性理論

最適化問題