多対一還元のソースを表示

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

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

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

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

もしそのような関数 ''f'' が存在するなら、''A'' は ''B'' に'''多対一還元可能'''または'''m-還元可能'''であると言い、次のように書く。
:<math>A \leq_m B.</math>
もし[[単射]]な多対一還元があるなら、''A'' は ''B'' に'''1-還元可能'''または'''一対一還元可能'''であると言い、次のように書く。
:<math>A \leq_1 B.</math>

===自然数の部分集合===
二つの集合 <math>A,B \subseteq \mathbb{N}</math> があるとする。何らかの[[計算可能関数|全体計算可能関数]] <math>f</math> が存在して <math>A = f^{-1}[B]</math> であるとき、<math>A</math> は <math>B</math> に'''多対一還元可能'''であると言い、次のように書く。
:<math>A \leq_m B.</math>
これに加えて <math>f</math> が[[単射]]である場合、<math>A</math> は <math>B</math> に'''1-還元可能'''であると言い、次のように書く。
:<math>A \leq_1 B.</math>

===多対一同値と1-同値===
<math>A \leq_m B \, \mathrm{and} \, B \leq_m A</math>であるとき、
<math>A</math> は <math>B</math> に'''多対一同値''' または '''m-同値''' であると言い、次のように書く。
:<math>A \equiv_m B.</math>

<math>A \leq_1 B \, \mathrm{and} \, B \leq_1 A</math>であるとき、
<math>A</math> は <math>B</math> に'''1-同値''' であると言い、次のように書く。
:<math>A \equiv_1 B.</math>

===多対一完全性（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 (計算量理論)|P]]、[[NP]]、[[L (計算量理論)|L]]、[[NL (計算量理論)|NL]]、[[co-NP]]、[[PSPACE]]、[[EXPTIME]]などがあり、他にも多数存在する。しかしながら、これらのクラスも任意の多対一還元の下で閉じている訳ではない。

==性質==
* 多対一還元や一対一還元は[[推移関係|推移的]]かつ[[反射関係|反射的]]であり、従って自然数の[[冪集合]]の上で[[順序集合|半順序]]を成す。
* <math>A \leq_m B</math> の[[必要十分条件]]は <math>\mathbb{N} \setminus A \leq_m \mathbb{N} \setminus B</math> である。
* ある集合が[[停止性問題|停止問題]]に多対一還元可能となる必要十分条件は、それが[[帰納的可算集合]]であることである。これは多対一還元に関する限り、あらゆる帰納的可算集合の中で停止問題が最も複雑であることを意味する。従って停止問題は多対一完全。
* ''個別の''チューリングマシン ''T'' に特化した停止問題（即ち、''T'' が最終的に停止するような入力の集合）が多対一完全である必要十分条件は ''T'' が[[チューリングマシン|万能チューリングマシン]]であることである。[[エミール・ポスト]]は[[決定可能]]でもm-完全でもない帰納的可算集合が存在することを示した。従って''固有の停止問題が決定不可能であるような万能<span style="text-decoration:underline;">でない</span>チューリングマシンが存在する''。（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

==脚注==
<references/>

{{DEFAULTSORT:たたいいちかんけん}}
[[Category:還元 (計算複雑性理論)]]
[[Category:数学に関する記事]]