多対一削減

計算可能性理論と 計算複雑性理論において、多対一縮約（マッピング縮約^[1]とも呼ばれる）は、計算可能関数を使用して、ある決定問題（インスタンスが にあるかどうか）のインスタンスを別の決定問題（インスタンスが にあるかどうか）に変換する縮約です。縮約されたインスタンスが言語 にあるのは、最初のインスタンスがその言語 にある場合のみです。したがって、インスタンスが言語 にあるかどうかを決定できる場合は、縮約を適用して を解くことで、インスタンスがその言語にあるかどうかを決定できます。したがって、縮約を使用して、2 つの問題の相対的な計算の難しさを測定できます。素人言葉で言えば、を解くのが と同じくらい難しい場合、 はに縮約されると言われています。これは、 を解くアルゴリズムはどれも、 を解く（それ以外は比較的単純な）プログラムの一部としても使用できることを意味します。 ${\displaystyle L_{1}}$${\displaystyle L_{2}}$${\displaystyle L_{2}}$${\displaystyle L_{1}}$${\displaystyle L_{2}}$${\displaystyle L_{2}}$${\displaystyle L_{1}}$${\displaystyle L_{2}}$${\displaystyle L_{1}}$${\displaystyle L_{2}}$${\displaystyle L_{2}}$${\displaystyle L_{1}}$${\displaystyle L_{2}}$${\displaystyle L_{1}}$

多対一還元は、チューリング還元の特殊なケースであり、より強力な形式です。^[1]多対一還元では、オラクル（つまり、 の解）は最後に一度だけ呼び出すことができ、答えを変更することはできません。つまり、問題 が問題 に還元できることを示す場合、の解の中で の解を一度だけ使用できます。チューリング還元では、の特定のインスタンスのメンバーシップ問題を解決するために、 の解を必要な回数だけ使用できます。 ${\displaystyle L_{2}}$${\displaystyle L_{1}}$${\displaystyle L_{2}}$${\displaystyle L_{2}}$${\displaystyle L_{1}}$${\displaystyle L_{2}}$${\displaystyle L_{1}}$

多対一還元は、 1944年にエミール・ポストが発表した論文で初めて使用されました。 ^[2]その後、ノーマン・シャピロは1956年に同じ概念を強い還元性という名前で使用しました。^[3]

およびがそれぞれアルファベットおよび上の形式言語であると仮定します。から への多対一還元は、各単語がにある場合、かつにある場合に限り、という特性を持つ全計算可能関数です。 ${\displaystyle A}$${\displaystyle B}$ ${\displaystyle \Sigma }$${\displaystyle \ガンマ}$${\displaystyle A}$${\displaystyle B}$ ${\displaystyle f:\Sigma ^{*}\rightarrow \Gamma ^{*}}$${\displaystyle w}$${\displaystyle A}$${\displaystyle f(w)}$${\displaystyle B}$

そのような関数が存在する場合、 は多対一還元可能またはm還元可能であり、次のように書くことができる 。${\displaystyle f}$${\displaystyle A}$${\displaystyle B}$

${\displaystyle A\leq _{\mathrm {m} }B.}$

2つの集合が与えられたとき、それは多対一還元可能であり、 ${\displaystyle A,B\subseteq \mathbb {N} }$${\displaystyle A}$${\displaystyle B}$

${\displaystyle A\leq _{\mathrm {m} }B}$

完全計算可能関数 が存在する場合、それは の場合も同様です。 ${\displaystyle f}$${\displaystyle x\in A}$${\displaystyle f(x)\in B}$

多対一還元が単射である場合、一対一還元と呼ばれ、 と書きます。 ${\displaystyle f}$${\displaystyle A\leq _{1}B}$

1対1還元が射影的である場合、 は と再帰的に同型であると言い、次のように書くことができる^{[4] p.324}${\displaystyle f}$${\displaystyle A}$${\displaystyle B}$

${\displaystyle A\equiv B}$

と の両方が成り立つ場合、は と多対一同値またはm 対同値であると言い、 と書く。 ${\displaystyle A\leq _{\mathrm {m} }B}$${\displaystyle B\leq _{\mathrm {m} }A}$${\displaystyle A}$${\displaystyle B}$

${\displaystyle A\equiv _{\mathrm {m} }B.}$

集合は、 が再帰的に列挙可能であり、すべての再帰的に列挙可能な集合がに m 簡約可能である場合に限り、多対一完全、または単にm 完全 と呼ばれます。 ${\displaystyle B}$ ${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$

関係は確かに同値であり、その同値類はm次と呼ばれ、によって誘導される順序を持つ順序集合を形成する。^{[4] p.257}${\displaystyle \equiv_{m}}$${\displaystyle {\mathcal {D}}_{m}}$${\displaystyle \leq _{m}}$

m次数のいくつかの性質、そのいくつかはチューリング次数の類似の性質とは異なる：^{[4] pp.555--581}

• m 次数には明確に定義されたジャンプ演算子があります。
• ジャンプが0 _m ′となる唯一の m 次数は0 _mです。
• が存在しないm 次数があります。${\displaystyle \mathbf {a} >_{m}{\boldsymbol {0}}_{m}'}$${\displaystyle \mathbf {b} }$${\displaystyle \mathbf {b} '=\mathbf {a} }$
• 最小元を持つすべての可算線形順序は に埋め込まれます。${\displaystyle {\mathcal {D}}_{m}}$
• の 1 階理論は2 階算術の理論と同型です。${\displaystyle {\mathcal {D}}_{m}}$

は、そのイデアルのいくつかの明示的な性質を満たす唯一の半順序集合として特徴付けられるが、チューリング度については同様の特徴付けは不可能である。^{[4] pp.574--575}${\displaystyle {\mathcal {D}}_{m}}$

マイヒルの同型定理は次のように述べることができる。「自然数のすべての集合に対して、」。系として、およびは同じ同値類を持つ。^{[4] p.325}の同値類は1 次と呼ばれる。 ${\displaystyle A,B}$${\displaystyle A\equiv B\iff A\equiv _{1}B}$${\displaystyle \equiv}$${\displaystyle \equiv_{1}}$${\displaystyle \equiv_{1}}$

多対一の縮約は、多くの場合、リソースの制約を受けます。たとえば、縮約関数は、多項式時間、対数空間、または回路、または後続の各縮約概念が前の縮約概念よりも弱い多対数射影によって計算可能です。詳細については、多項式時間縮約と対数空間縮約を参照してください。 ${\displaystyle AC_{0}}$${\displaystyle NC_{0}}$

決定問題およびとのインスタンスを解くアルゴリズムNが与えられた場合、からへの多対一還元を使用して のインスタンスを解くことができます。 ${\displaystyle A}$${\displaystyle B}$ ${\displaystyle B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$

• Nに必要な時間と削減に必要な時間の合計
• Nに必要なスペースと縮小に必要なスペースの最大値

言語のクラスC (または自然数のべき集合のサブセット) が多対一還元可能性に関して閉じているとは、 Cの外部の言語から C 内の言語への還元が存在しないことを意味します。クラスが多対一還元可能性に関して閉じている場合、多対一還元を使用して、問題を C 内の問題に還元することにより、問題が C 内にあることを示すことができます。多対一還元が有用なのは、よく研究されている複雑性クラスの大部分が、 P、NP、L、NL、co-NP、PSPACE、EXPなど、何らかの種類の多対一還元可能性に関して閉じているためです。たとえば、最初に挙げた 4 つは、多重対数時間射影という非常に弱い還元概念まで閉じていることが知られています。ただし、これらのクラスは任意の多対一還元に関して閉じているわけではありません。

多対一還元の一般化されたケースについても尋ねられるかもしれません。そのような例の 1 つはe 還元で、ここではが再帰的 に制限されるのではなく、再帰的に可算であるとみなします。結果として生じる還元関係は と表記され、その半集合はチューリング次数の場合と同様に研究されてきました。たとえば、e次数にはジャンプ セットがあります。e次数は、チューリング次数の半集合とは異なるいくつかの特性、たとえば 未満の次数へのダイヤモンド グラフの埋め込みを許容します。^[5]${\displaystyle f:A\to B}$${\displaystyle f}$${\displaystyle \leq _{e}}$${\displaystyle {\boldsymbol {0}}_{e}^{'}}$${\displaystyle {\boldsymbol {'}}_{e}}$

• 多対一の還元可能性と 1 対一の還元可能性の関係は推移的かつ反射的であり、したがって自然数のべき集合に事前順序を誘導します。
• ${\displaystyle A\leq _{\mathrm {m} }B}$ もし、もし、 ${\displaystyle \mathbb {N} \setminus A\leq _{\mathrm {m} }\mathbb {N} \setminus B.}$
• 集合が停止問題 に多対一還元可能であるのは、それが再帰的に可算である場合に限ります。これは、多対一還元可能性に関して、停止問題がすべての再帰的に可算な問題の中で最も複雑であることを示しています。したがって、停止問題は再完全です。これが唯一の再完全問題ではないことに注意してください。
• 個々のチューリングマシンTの特殊な停止問題(つまり、T が最終的に停止する入力の集合) は、T が万能チューリングマシンである場合に限り、多対一完全です。エミール・ポストは、決定可能でも m 完全でもない再帰的に列挙可能な集合が存在し、したがって、個々の停止問題がそれでも決定不可能である非万能チューリングマシンが存在することを示しまし た。

問題Aから問題Bへの多項式時間多対一縮約(通常は両方とも決定問題であることが要求される) は、問題Aへの入力を問題Bへの入力に変換し、変換された問題が元の問題と同じ出力を持つようにする多項式時間アルゴリズムである。問題Aのインスタンスx は、この変換を適用して問題Bのインスタンスy を生成し、 y を問題Bのアルゴリズムの入力として与え、その出力を返すことで解決できる。多項式時間多対一縮約は、リチャード・カープにちなんで多項式変換またはカープ縮約とも呼ばれる。このタイプの縮約は、またはで表される。^{[6] [7]}${\displaystyle A\leq _{m}^{P}B}$${\displaystyle A\leq _{p}B}$