FP（複雑性）

計算複雑性理論において、複雑性クラスFP は、決定性チューリングマシンによって多項式時間で解ける関数問題の集合であり、（関数問題が多項式時間で決定可能な述語を表す場合） ^{[ 1 ]}である。これは、決定問題クラスPの関数問題版である。大まかに言えば、ランダム化なしで古典コンピュータ上で効率的に計算できる関数のクラスである。

FPとPの違いは、 Pの問題は1ビットのイエス/ノーの答えを持つのに対し、FPの問題は多項式時間で計算できる任意の出力を持つことができる点です。たとえば、2つの数を足すのはFPの問題ですが、その合計が奇数かどうかを判定するのはPの問題です。^{[ 2 ]}したがって、 P の任意の決定問題は、0または1を出力する関数と考えることができるため、自明にFPに属します。要するに、${\displaystyle {\mathsf {P}}\subseteq {\mathsf {FP}}}$。

多項式時間関数問題は、多項式時間還元を定義する上で基本的であり、多項式時間還元は、 NP完全問題のクラスを定義するために用いられる。^{[ 3 ]}

FPは正式には以下のように定義される。

二項関係${\displaystyle R}$FPに含まれるのは、

• 与えられた条件を満たす決定論的な多項式時間アルゴリズムが存在する。${\displaystyle x}$どちらかが何かを見つける${\displaystyle y}$そのため${\displaystyle R(x,y)}$保持する、またはそのようなものは存在しないことを知らせる${\displaystyle y}$存在する、

• そして、与えられた条件に基づいて、決定論的アルゴリズムが存在する。${\displaystyle x}$そして${\displaystyle y}$、チェックします${\displaystyle R(x,y)}$保持し、サイズの多項式時間で実行されます${\displaystyle x}$。

（後者の条件は冗長に見えるかもしれないが、複数のFP問題が存在する可能性があるため、すべてのFP問題がFNPに属することを保証するために追加されている。）${\displaystyle y}$値${\displaystyle R(x,y)}$（ただし、2番目の条件が満たされない場合、アルゴリズムはこれらの値をそれぞれ多項式時間でチェックできる必要はない。）

• FNP は、 xとyが与えられたときにR ( x , y ) が成り立つかどうかをチェックし、 xのサイズの多項式時間で実行される決定論的アルゴリズムが存在する二項関係Rの集合とFP が密接に関連しているのと同様に、 NP はFNPと密接に関連しています。FP= FNP は、P = NPの場合に限り成り立ちます。
• 対数空間を使用する機械は、構成が多項式個しかないため、対数空間で計算可能な関数問題の集合であるFLはFPに含まれます。FLとFPが等しいかどうかは不明です。これは、決定クラスPとLが等しいかどうかを判断する問題に類似しています。

• 複雑性動物園：FP