関数問題
(Function problem から転送)
出典: フリー百科事典『ウィキペディア（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に含まれるより具体的な問題のクラス。
主な関数問題
- 充足割り当て問題
- 決定問題である充足可能性問題と対比してこう書かれる。
- 最大クリーク問題
- 巡回セールスマン問題
関連項目
「Function problem」の例文・使い方・用例・文例
「Function problem」に関係したコラム
FXのチャート分析ソフトMT4で10分足や2時間足などを表示するには
FX（外国為替証拠金取引）のチャート分析ソフトMT4（Meta Trader 4）では、次の時間足の表示ができます。ティック1分足5分足15分足30分足1時間足4時間足日足週足MT4では、10分足や1...
- Function problemのページへのリンク
