多対一還元（たたいいちかんげん、many-one reduction）とは、計算理論と計算量理論におけるある種の還元操作の名前。何らかの決定問題を他の決定問題に変換する働きを持つ。多対一還元はチューリング還元の特殊ケースであり、チューリング還元よりも弱い（多対一還元可能であるという主張はチューリング還元可能よりも強い）。多対一還元においては、オラクルの使用（神託機械参照）は一度だけ、そして最後にだけ許される。多対一還元は1944年、エミール・ポストによって初めて導入された。1956年、Norman Shapiro は同じ概念を "strong reducibility" という名前で適用した。"A" と "B" をそれぞれアルファベットの集合 Σ と Γの上で書かれた形式言語だとしよう。"A" から "B" への多対一還元とは、次の性質を満たすような全体計算可能関数 "f" : Σ → Γ を指す。性質：「個々の単語 "w" が "A" の中にある必要十分条件が、『"f"("w") が "B" の中にあること』（即ち、formula_1）である」。もしそのような関数 "f" が存在するなら、"A" は "B" に多対一還元可能またはm-還元可能であると言い、次のように書く。もし単射な多対一還元があるなら、"A" は "B" に1-還元可能または一対一還元可能であると言い、次のように書く。二つの集合 formula_4 があるとする。何らかの全体計算可能関数 formula_5 が存在して formula_6 であるとき、formula_7 は formula_8 に多対一還元可能であると言い、次のように書く。これに加えて formula_5 が単射である場合、formula_7 は formula_8 に1-還元可能であると言い、次のように書く。formula_14であるとき、formula_7 は formula_8 に多対一同値 または m-同値 であると言い、次のように書く。formula_18であるとき、formula_7 は formula_8 に1-同値 であると言い、次のように書く。帰納的可算集合 "B" が存在し、全ての帰納的可算集合 "A" が "B" に m-還元可能であるとき、"B" は多対一完全またはm-完全であると言う。多対一還元は計算資源の制限と合わせて論じられることが多い。例えばその還元関数が多項式時間や対数領域で計算可能か、などである。詳しくは多項式時間還元と対数領域還元を参照のこと。決定問題 "A" と "B" があり、また "B" を解けるアルゴリズム "N" があるとする。このとき、"A" を "B" に多対一還元できるなら、"N" を応用して "A" を解けるが、この時のコストは次の通りとなる。何らかの言語（または、自然数の集合）のクラス C について、C に含まれない言語を C に含まれる言語へ多対一還元できないとき、C は「多対一還元の下で閉じている」と言う。もし C が多対一還元の下で閉じているなら、C に含まれる問題を他の問題に多対一還元できた場合、その還元もとの問題も C に含まれることが言える。多対一還元が便利なのは、よく知られている計算量の殆どは何らかの多対一還元の下で閉じているからである。このようなクラスとしては P、NP、L、NL、co-NP、PSPACE、EXPTIMEなどがあり、他にも多数存在する。しかしながら、これらのクラスも任意の多対一還元の下で閉じている訳ではない。

出典:wikipedia