多対一還元

多対一還元（たたいいちかんげん、many-one reduction）とは、計算理論と計算量理論におけるある種の還元操作の名前。何らかの決定問題を他の決定問題に変換する働きを持つ。

多対一還元はチューリング還元の特殊ケースであり、チューリング還元よりも弱い（多対一還元可能であるという主張はチューリング還元可能よりも強い）。多対一還元においては、オラクルの使用（神託機械参照）は一度だけ、そして最後にだけ許される。

多対一還元は1944年、エミール・ポストによって初めて導入された。1956年、Norman Shapiro は同じ概念を strong reducibility という名前で適用した。

定義

形式言語

A と B をそれぞれアルファベットの集合 Σ と Γの上で書かれた形式言語だとしよう。A から B への多対一還元とは、次の性質を満たすような全体計算可能関数 f : Σ^* → Γ^* を指す。性質：「個々の単語 w が A の中にある必要十分条件が、『f(w) が B の中にあること』（即ち、${\displaystyle A=f^{-1}(B)}$）である」。

もしそのような関数 f が存在するなら、A は B に多対一還元可能またはm-還元可能であると言い、次のように書く。

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

もし単射な多対一還元があるなら、A は B に1-還元可能または一対一還元可能であると言い、次のように書く。

${\displaystyle A\leq _{1}B.}$

自然数の部分集合

二つの集合 ${\displaystyle A,B\subseteq \mathbb {N} }$ があるとする。何らかの全体計算可能関数 ${\displaystyle f}$ が存在して ${\displaystyle A=f^{-1}[B]}$ であるとき、${\displaystyle A}$ は ${\displaystyle B}$ に多対一還元可能であると言い、次のように書く。

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

これに加えて ${\displaystyle f}$ が単射である場合、${\displaystyle A}$ は ${\displaystyle B}$ に1-還元可能であると言い、次のように書く。

${\displaystyle A\leq _{1}B.}$

多対一同値と1-同値

${\displaystyle A\leq _{m}B\,\mathrm {and} \,B\leq _{m}A}$であるとき、 ${\displaystyle A}$ は ${\displaystyle B}$ に多対一同値 または m-同値 であると言い、次のように書く。

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

${\displaystyle A\leq _{1}B\,\mathrm {and} \,B\leq _{1}A}$であるとき、 ${\displaystyle A}$ は ${\displaystyle B}$ に1-同値 であると言い、次のように書く。

${\displaystyle A\equiv _{1}B.}$

多対一完全性（m-完全性）

帰納的可算集合 B が存在し、全ての帰納的可算集合 A が B に m-還元可能であるとき、B は多対一完全またはm-完全であると言う。

資源制限つきの多対一還元

多対一還元は計算資源の制限と合わせて論じられることが多い。例えばその還元関数が多項式時間や対数領域で計算可能か、などである。詳しくは多項式時間還元と対数領域還元を参照のこと。

決定問題 A と B があり、また B を解けるアルゴリズム N があるとする。このとき、A を B に多対一還元できるなら、N を応用して A を解けるが、この時のコストは次の通りとなる。

• N を実行するのに必要な時間＋還元に必要な時間
• N を実行するのに必要な最大領域＋還元に必要な領域

何らかの言語（または、自然数の集合）のクラス C について、C に含まれない言語を C に含まれる言語へ多対一還元できないとき、C は「多対一還元の下で閉じている」と言う。もし C が多対一還元の下で閉じているなら、C に含まれる問題を他の問題に多対一還元できた場合、その還元もとの問題も C に含まれることが言える。多対一還元が便利なのは、よく知られている計算量の殆どは何らかの多対一還元の下で閉じているからである。このようなクラスとしては P、NP、L、NL、co-NP、PSPACE、EXPTIMEなどがあり、他にも多数存在する。しかしながら、これらのクラスも任意の多対一還元の下で閉じている訳ではない。

性質

• 多対一還元や一対一還元は推移的かつ反射的であり、従って自然数の冪集合の上で半順序を成す。
• ${\displaystyle A\leq _{m}B}$ の必要十分条件は ${\displaystyle \mathbb {N} \setminus A\leq _{m}\mathbb {N} \setminus B}$ である。
• ある集合が停止問題に多対一還元可能となる必要十分条件は、それが帰納的可算集合であることである。これは多対一還元に関する限り、あらゆる帰納的可算集合の中で停止問題が最も複雑であることを意味する。従って停止問題は多対一完全。
• 個別のチューリングマシン T に特化した停止問題（即ち、T が最終的に停止するような入力の集合）が多対一完全である必要十分条件は T が万能チューリングマシンであることである。エミール・ポストは決定可能でもm-完全でもない帰納的可算集合が存在することを示した。従って固有の停止問題が決定不可能であるような万能でないチューリングマシンが存在する。（c.f. 単純集合）

参考文献

• E. L. Post, "Recursively enumerable sets of positive integers and their decision problems", Bulletin of the American Mathematical Society 50 (1944) 284-316
• Norman Shapiro, "Degrees of Computability", Transactions of the American Mathematical Society 82, (1956) 281-299

脚注