機能の問題

計算複雑性理論において、関数問題とは、あらゆる入力に対して単一の出力が期待される計算問題であるが、その出力は決定問題の出力よりも複雑である。関数問題の場合、出力は単純に「はい」または「いいえ」ではない。

関数の問題${\displaystyle P}$関係によって定義される${\displaystyle R}$任意のアルファベットの文字列に対して${\displaystyle \Sigma }$:

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

ご了承ください${\displaystyle R}$関数的な二項関係である必要はない。

アルゴリズムが解決する${\displaystyle P}$すべての入力に対して${\displaystyle x}$存在する${\displaystyle y}$満足${\displaystyle (x,y)\in R}$アルゴリズムは、そのようなものを1つ生成する。${\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}}}$あるいは、そのような割り当ては存在しないと判断する。

この場合、関係${\displaystyle R}$は、適切に符号化された命題論理式と充足割り当てのペアによって与えられる。一方、SATアルゴリズムは、論理式を入力として受け取る。${\displaystyle \varphi }$FSAT アルゴリズムは、「充足不可能」または「充足可能」を返すだけでよく、後者の場合は何らかの充足割り当てを返す必要があります。

その他の注目すべき例としては、セールスマンがたどった経路を求める巡回セールスマン問題や、因数の一覧を求める整数因数分解問題などが挙げられる。

任意の決定問題を考える${\displaystyle L}$クラスNPに属する。NPの定義により、各問題インスタンスが${\displaystyle x}$「はい」と答えられるものは多項式サイズの証明書を持っています${\displaystyle y}$これは「はい」という回答の証明として機能します（そして「いいえ」と答えられた問題インスタンスにはそのような証明書はありません）。したがって、これらのペアのセットは${\displaystyle (x,y)}$関数問題「与えられた」を表す関係を形成する${\displaystyle x}$で${\displaystyle L}$証明書を見つける${\displaystyle y}$のために${\displaystyle x}$この関数問題は、${\displaystyle L}$; これはFNPクラスに属します。

逆に、 FNPのすべての問題R は、(一意の) 対応する決定問題を誘発します。つまり、 xが与えられたとき、 R ( x , y ) が成り立つようなyが存在するかどうかを決定してください。

FNPはNPの関数クラス版と考えることができる。FNP問題の解は効率的に（すなわち、入力の長さに対して多項式時間で）検証できるが、必ずしも効率的に見つけられるとは限らない。対照的に、Pの関数クラス版と考えることができるFPクラスは、解を多項式時間で見つけることができる関数問題から構成される。

上記で紹介したFSAT問題は、SAT問題を判定するサブルーチンへの呼び出しを多項式回数だけ使用して解決できることに注目してください。アルゴリズムはまず、式が正しいかどうかを尋ねます。${\displaystyle \varphi }$は充足可能である。その後、アルゴリズムは変数を固定することができる。${\displaystyle x_{1}}$TRUE にして再度質問します。結果として得られた式がまだ充足可能であれば、アルゴリズムは続行します。${\displaystyle x_{1}}$TRUEに固定され、修正が継続されます${\displaystyle x_{2}}$そうでなければ、${\displaystyle x_{1}}$は FALSE でなければならず、継続します。したがって、FSAT はSATを決定するオラクルを使用して多項式時間で解くことができます。一般に、 FNPの問題は、誘導された決定問題に対するオラクルを使用して多項式時間で解くことができる場合、自己還元可能と呼ばれます。すべてのNP 完全問題のすべての関数バリアントは自己還元可能です。自己還元性にはいくつかの (わずかに異なる) 概念があります。^{[ 1 ] [ 2 ] [ 3 ]}

関数問題は、決定問題とよく似た形で簡略化できる。与えられた関数問題${\displaystyle R}$そして${\displaystyle S}$私たちは言う${\displaystyle R}$に縮小${\displaystyle 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困難問題を定義することが可能である。

問題${\displaystyle R}$FNPのすべての問題が に還元できる場合、 はFNP 困難です。${\displaystyle R}$問題${\displaystyle R}$FNP困難かつFNPに属する場合、FNP完全である。問題FSATはFNP完全問題であり、したがってFSATの自己還元性により、${\displaystyle \mathbf {P} =\mathbf {NP} }$かつその場合に限り$\displaystyle \mathbf {FP} =\mathbf {FNP} }$。

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

• 意思決定問題
• 検索問題
• 計数問題（複雑性）
• 最適化問題