関数問題の主なクラス
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2014/08/22 21:35 UTC 版)
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に含まれるより具体的な問題のクラス。
※この「関数問題の主なクラス」の解説は、「関数問題」の解説の一部です。
「関数問題の主なクラス」を含む「関数問題」の記事については、「関数問題」の概要を参照ください。
ウィキペディア小見出し辞書の「関数問題の主なクラス」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 関数問題の主なクラスのページへのリンク
