機能の問題

計算複雑性理論では、関数問題とは、すべての入力に対して単一の出力（全関数）が期待される計算問題ですが、出力は決定問題よりも複雑です。関数問題の場合、出力は単純に「はい」または「いいえ」ではありません。

関数問題は、任意のアルファベットの文字列の関係によって定義されます。 ${\displaystyle P}$ ${\displaystyle R}$ ${\displaystyle \Sigma }$

${\displaystyle R\subseteq \Sigma ^{*}\times \Sigma ^{*}.}$

アルゴリズムは、を満たす が存在するような入力ごとに を解決し、そのような を 1 つ生成し、そのような が存在しない場合はを拒否します。 ${\displaystyle P}$${\displaystyle x}$${\displaystyle y}$${\displaystyle (x,y)\in R}$${\displaystyle y}$${\displaystyle y}$

プロミス関数の問題は、そのようなものが存在しない場合は何でも実行できます (したがって終了しない可能性があります) 。 ${\displaystyle y}$

よく知られている関数の問題は、関数ブール充足可能性問題 (略してFSAT)です。この問題はSAT決定問題と密接に関連しており、次のように定式化できます。

変数 を含むブール式が与えられた場合、 がに評価されるような割り当てを見つけるか、そのような割り当てが存在しないことを確認します。${\displaystyle \varphi}$${\displaystyle x_{1},\ldots ,x_{n}}$${\displaystyle x_{i}\rightarrow \{{\text{TRUE}},{\text{FALSE}}\}}$${\displaystyle \varphi}$${\displaystyle {\text{TRUE}}}$

この場合、関係は、適切にエンコードされたブール式と満足する割り当てのタプルによって与えられます。式が入力された SAT アルゴリズムは、「満足できない」または「満足できる」を返すだけで済みますが、FSAT アルゴリズムは後者の場合に満足する割り当てを返す必要があります。 ${\displaystyle R}$${\displaystyle \varphi}$

その他の注目すべき例としては、セールスマンがたどるルートを尋ねる巡回セールスマン問題や、因数のリストを尋ねる 整数因数分解問題などがあります。

クラスNPの任意の決定問題を考えてみましょう。 NPの定義により、「はい」と答えられる各問題インスタンスには、「はい」の答えの証明として機能する多項式サイズの証明書があります。したがって、これらのタプルのセットは関係を形成し、「で与えられた場合、の証明書を見つける」という関数問題を表します。この機能問題はの関数バリアントと呼ばれ、クラスFNPに属します。 ${\displaystyle L}$${\displaystyle x}$${\displaystyle y}$${\displaystyle (x,y)}$${\displaystyle x}$${\displaystyle L}$${\displaystyle y}$${\displaystyle x}$${\displaystyle L}$

FNP はNPの関数クラス類似物と考えることができます。つまり、FNP問題の解は効率的に（つまり、入力の長さに関して多項式時間で）検証できますが、必ずしも効率的に見つかるとは限りません。対照的に、 Pの関数クラス類似物と考えることができるクラスFPは、多項式時間で解が見つかる関数問題で構成されます。

上で紹介した問題FSAT は、 SAT問題を決定するサブルーチンへの多項式回数の呼び出しのみを使用して解決できることに注目してください。アルゴリズムは、最初に式が満足可能かどうかを尋ねることができます。その後、アルゴリズムは変数 をTRUE に固定して再度尋ねることができます。結果の式がまだ満足可能であれば、アルゴリズムは をTRUE に固定したまま を固定し続け、そうでない場合は をFALSE にする必要があると判断して続行します。したがって、FSAT は、SAT を決定するオラクルを使用して多項式時間で解決できます。一般に、NPの問題は、その関数バリアントが元の問題を決定するオラクルを使用して多項式時間で解決できる場合、自己還元可能と呼ばれます。すべてのNP 完全問題は自己還元可能です。整数因数分解問題は自己還元可能ではないと推測されています^{[誰によって? ]。}これは、整数が素数かどうかの決定はP内にある(簡単)ためです^[1] 。一方、整数因数分解問題は古典的コンピュータにとっては困難であると考えられています。自己還元性にはいくつかの（わずかに異なる）概念がある。^{[2] [3] [4]}${\displaystyle \varphi}$${\displaystyle x_{1}}$${\displaystyle x_{1}}$${\displaystyle x_{2}}$${\displaystyle x_{1}}$

関数の問題は、決定問題とよく似た方法で簡約することができます。関数の問題とが与えられたとき、多項式時間で計算可能な関数とが存在し、のすべてのインスタンスと の可能な解に対して、がに簡約されると言えます。 ${\displaystyle \Pi_{R}}$${\displaystyle \Pi_{S}}$${\displaystyle \Pi_{R}}$${\displaystyle \Pi_{S}}$${\displaystyle f}$${\displaystyle g}$${\displaystyle x}$${\displaystyle R}$${\displaystyle y}$${\displaystyle S}$

• に -解がある場合、 には-解があります。${\displaystyle x}$${\displaystyle R}$${\displaystyle f(x)}$${\displaystyle S}$
• ${\displaystyle (f(x),y)\in S\implies (x,g(x,y))\in R.}$

したがって、 NP完全問題に類似した FNP完全問題を定義することが可能です。

問題がFNP 完全であるとは、 FNPのすべての問題が に簡約できる場合です。FNP完全問題の複雑性クラスは、 FNP-CまたはFNPCで示されます。したがって、問題FSATもFNP 完全問題であり、の場合にのみが成立します。 ${\displaystyle \Pi_{R}}$${\displaystyle \Pi_{R}}$${\displaystyle \mathbf {P} =\mathbf {NP} }$${\displaystyle \mathbf {FP} =\mathbf {FNP} }$

関数問題を定義するために使用される関係には、不完全であるという欠点があります。つまり、すべての入力に、となる対応するものが存在するわけではありません。したがって、証明の計算可能性の問題は、それらの存在の問題から切り離せません。この問題を克服するには、関数問題を全関係に制限して、FNPのサブクラスとしてクラスTFNPを生成すると便利です。このクラスには、解が存在することが保証されている特定の戦略ゲームにおける純粋ナッシュ均衡の計算などの問題が含まれます。さらに、TFNP にFNP 完全問題が含まれている場合は、 が成り立ちます。 ${\displaystyle R(x,y)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle (x,y)\in R}$${\displaystyle \mathbf {NP} ={\textbf {co-NP}}}$

• 決定問題
• 検索の問題
• 数え上げ問題（複雑さ）
• 最適化問題