FNP（複雑さ）

計算複雑性理論では、複雑性クラス FNP は、決定問題クラスNPの関数問題拡張です。次の正式な定義で説明されているように、技術的には関数ではなく、 2 項関係のクラスであるため、この名前は多少誤解を招きます。

二項関係P( x , y )（yは最大でもxより多項式長である）がFNPに属するのは、 xとyの両方が与えられたときにP( x , y )が成り立つかどうかを判定できる決定論的多項式時間アルゴリズムが存在する場合のみである。^[1]

この定義は非決定性を含まず、NP の検証者定義に類似しています。

すべての FNP 関係に直接対応する NP 言語があり、これはFNP 関係によって誘導される、またはFNP 関係に対応する決定問題と呼ばれることもあります。これは、あるyが与えられたときに P( x、y ) が成り立つすべてのx を取ることによって形成される言語です。ただし、特定の決定問題には複数の FNP 関係が存在する場合があります。

NP の多くの問題、特にNP 完全問題は、特定のオブジェクトが存在するかどうかを問うものであり、たとえば、満足な割り当て、グラフの色付け、特定のサイズのクリークなどがある。これらの問題は、オブジェクトが存在するかどうかだけでなく、そのようなオブジェクトがどのような値を持つことができるかを問う FNP の問題に対応することが多い。FNP 問題がこのように NP 完全問題に対応する場合、その問題はNP 困難である。Bellare と Goldwasser は 1994 年に、いくつかの標準的な仮定を使用して、NP には FNP バージョンが自己還元可能でない問題が存在することを示し、これは対応する決定問題よりも困難であることを意味している。^[2]

FNP 内の各 P( x , y ) について、 P( x , y )に関連付けられた検索問題は、 xが与えられた場合、 P( x , y ) が成り立つようなy を見つけるか、そのようなy が存在しないと述べることです。 FNP 内のすべての関係の検索問題は、 P = NP の場合にのみ多項式時間で解決できます。 この結果は通常、「P = NPの場合にのみFP = FNP 」と表現されますが、このステートメントが真であるためには、 FP と FNP のメンバーが関係ではなく、関係に関連付けられた検索問題になるように FP と FNP を再定義する必要があります。

P ₁とP _{2 を}FNPの2つの問題とし、関連する検証アルゴリズムA ₁、A ₂があるとする 。縮約P ₁とP _{2 は、2つの効率的に計算可能な関数}fとgとして定義され、^[3]

• fはP1_への入力xをP2_への入力f ( x )にマッピングします 。
• gは出力yをP ₂にマッピングし、出力g (y)をP ₁にマッピングします 。
• すべてのxとyについて、A ₂ ( f ( x ), y ) が true を返す場合、A ₁ ( x , g( y )) は true を返します。
• すべてのxについて: A ₂ ( f ( x ), y ) がすべてのyに対して false を返す場合、A ₁ ( x , g( y )) はすべてのyに対して false を返します。

• FP は、 xが与えられたときに P( x , y ) が成り立つy を見つける多項式時間アルゴリズムが存在する二項関係の集合です。 FNP と FP の関係は、 NP と P の関係に類似しています。
• TFNPはFNPのサブセットです。TFNPには、FNP内の関係のうち、任意のxに対して、 P( x , y )が成り立つ少なくとも1つのyが存在する関係が含まれます。

• 複雑性動物園：FNP