多対一還元

計算可能性理論と 計算複雑性理論において、多対一縮約（写像縮約^[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_{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 \Gamma}$ ${\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.}$

自然数の部分集合

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

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

完全 に計算可能な関数が存在する場合、それはiff です。 ${\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完全であるとは、その集合が再帰的に可算であり、すべての再帰的に可算な集合が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}}$
• の第一階理論は第二階算術の理論と同型です。${\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}}$

性質

• 多対一還元可能性と一還元可能性の関係は推移的かつ反射的であり、したがって自然数の冪集合に前順序を誘導します
• ${\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}$

参考文献

1. アブラハムソン、カール・R.（2016年春）「マッピング縮小」。CSCI 6420 – 計算可能性と複雑性。イーストカロライナ大学。 2021年11月12日閲覧
2. EL Post、「正整数の再帰的に列挙可能な集合とその決定問題」、アメリカ数学会報 50 (1944) 284–316
3. ノーマン・シャピロ、「計算可能性の度合い」、アメリカ数学会誌 82、(1956)281–299
4. P. Odifreddi ,古典的再帰理論：関数と自然数集合の理論（p.320）. 論理学と数学の基礎研究, 第125巻 (1989), Elsevier 0-444-87295-7.
5. S. Ahmad, Σ 2 {\displaystyle \Sigma _{2}} 列挙次数へのダイヤモンドの埋め込み (1991). Journal of Symbolic Logic , vol.56.
6. Goldreich, Oded (2008),計算複雑性：概念的視点、ケンブリッジ大学出版局、pp.  59– 60、ISBN 9781139472746
7. クラインバーグ、ジョン、タルドス、エヴァ(2006).アルゴリズム設計. ピアソン・エデュケーション. pp.  452– 453. ISBN 978-0-321-37291-8。