多対一削減

計算可能性理論および 計算複雑性理論において、多対一還元（マッピング還元とも呼ばれる^{[ 1 ]}）は、 1つの決定問題（インスタンスがであるかどうか）のインスタンスを変換する還元である。${\displaystyle L_{1}}$）別の決定問題（インスタンスが${\displaystyle L_{2}}$計算可能な関数を使用して、縮小されたインスタンスは次の言語で表されます。${\displaystyle L_{2}}$最初のインスタンスがその言語である場合に限る${\displaystyle L_{1}}$したがって、もし私たちが決定できるならば${\displaystyle L_{2}}$言語の例${\displaystyle L_{2}}$私たちは、${\displaystyle L_{1}}$言語の例${\displaystyle L_{1}}$還元法を適用して解くことで${\displaystyle L_{2}}$したがって、還元法は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 \equiv _{m}}$確かに同値関係であり、その同値類はm次数と呼ばれ、半順序集合を形成する。$\displaystyle {\mathcal {D}}_{m}}$によって誘導される秩序$\leq _{m}}$[ ^{4 ] p.257​}

m次数のいくつかの特性（チューリング次数の類似特性とは異なるものもある） ：^{[ 4 ] 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}}$。
• 第一階理論$\displaystyle {\mathcal {D}}_{m}}$これは、2階算術の理論と同型である。

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

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

多対一還元は、多くの場合、リソースの制約を受けます。たとえば、還元関数が多項式時間、対数空間で計算可能であること、$\displaystyle AC_0$または$NC0$回路、または多対数射影であり、後続の各削減概念は前のものよりも弱い。詳細については、多項式時間削減および対数空間削減を参照のこと。

与えられた意思決定問題${\displaystyle A}$そして${\displaystyle B}$そして、インスタンスを解決するアルゴリズムN${\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還元であり、ここでは${\displaystyle f:A\to B}$再帰的に列挙可能なものであって、再帰的に制限するものではない${\displaystyle f}$結果として得られる還元関係は、$\leq _{e}}$、そしてその半順序集合はチューリング次数と同様の方法で研究されてきた。例えば、ジャンプ集合が存在する。${\displaystyle {\boldsymbol {0}}_{e}^{'}}$e-次数について。e-次数は、チューリング次数の半順序集合とは異なるいくつかの性質を持ちます。例えば、ダイヤモンドグラフを以下の次数に埋め込むことができます。${\displaystyle {\boldsymbol {'}}_{e}}$[ ^{5 ]​}

• 多対一還元性と一対一還元性の関係は推移的かつ反射的であるため、自然数の冪集合上に前順序を誘導する。
• ${\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のアルゴリズムへの入力として与え、その出力を返すことによって解くことができます。多項式時間多対一還元は、多項式変換またはリチャード・カープにちなんでカープ還元とも呼ばれます。このタイプの還元は、次のように表されます。${\displaystyle A\leq _{m}^{P}B}$または${\displaystyle A\leq _{p}B}$[ ^{6 ] [ 7 ]​}