多対一還元
多対一還元(たたいいちかんげん、many-one reduction)とは、計算理論と計算量理論におけるある種の還元操作の名前。何らかの決定問題を他の決定問題に変換する働きを持つ。
多対一還元はチューリング還元の特殊ケースであり、チューリング還元よりも弱い(多対一還元可能であるという主張はチューリング還元可能よりも強い)。多対一還元においては、オラクルの使用(神託機械参照)は一度だけ、そして最後にだけ許される。
多対一還元は1944年、エミール・ポストによって初めて導入された。1956年、Norman Shapiro は同じ概念を strong reducibility という名前で適用した。
多対一還元は計算資源の制限と合わせて論じられることが多い。例えばその還元関数が多項式時間や対数領域で計算可能か、などである。詳しくは多項式時間還元と対数領域還元を参照のこと。
決定問題 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などがあり、他にも多数存在する。しかしながら、これらのクラスも任意の多対一還元の下で閉じている訳ではない。