多対一還元
Many-one reduction
チューリング還元よりも、強い主張
厳しい、範囲が狭い主張mrsekut.icon
定義
自然数の集合$ \alpha,\betaに対して以下の条件が成り立つとき$ \alpha\le_m\betaと書く
計算可能1変数全域関数$ fが存在して、任意の自然数$ xに対して以下が成り立つ
$ x\in\alpha \iff f(x)\in\beta
https://gyazo.com/33b99d225aa2af369854cb20ef5eb8a4
$ fは逆写像も、単射、全射であるかどうかも定義されていないことに注意mrsekut.icon
なので下図のようになることもありうる
https://gyazo.com/5413ff01e6e2e67edb24a2487cb4bc46
$ \alpha\equiv_m\betaのことを多対一同値と言う $ \alpha\le_m\betaの「$ \betaの方が優位」なことのイメージ
上の定義より、$ x\in\alpha\iff f(x)\in\betaなので、
$ \betaの内容が全て明らかな場合は、
$ fを使うことで$ \alphaを復元できる
e.g. 「10」は$ \alphaに入っていますか？のような問題にyes/noで答えられる
仮に、$ f(x)=x*0のような帰着関数の場合は、自明に、$ \alphaのほうが単純であることがわかる
逆は成り立たない
$ x\in\alphaに対して、$ f(x)を集めたものが$ \betaとイコールになるとは限らない
https://gyazo.com/5413ff01e6e2e67edb24a2487cb4bc46
定理
$ \alpha\le_m\betaならば$ \alpha\le_T\betaである
従って、$ \alpha\equiv_m\betaならば$ \alpha\equiv_T\betaである
$ \alpha\equiv_T\betaかつ$ \alpha\not \equiv_m\betaであるような$ \alpha,\betaが存在する
e.g. $ \alpha=\mathrm{HaltPair}, \beta=\overline{\mathrm{HaltPair}}
補足
下図はイメージであって厳密な何かではないmrsekut.icon
https://gyazo.com/d15cc5095707d1a8d2532cdf4d90d010
定理
$ \betaが$ \Sigma_n集合で$ \alpha\le_m\betaならば、$ \alphaも$ \Sigma_n集合である
従って、$ \betaが$ \Sigma_n集合で$ \alpha\equiv_m\betaならば、$ \alphaも$ \Sigma_n集合である
$ \le_mよりも$ \equiv_mの方が厳しいので、前者で成り立つなら後者でも成り立つmrsekut.icon
$ \Sigma_nを$ \Pi_nに換えても成り立つmrsekut.icon
e.g. haltPairは②に属し、その補集合は③に属し、これらはチューリング同値 https://gyazo.com/8729669484500c4bca845acb6f4245c6
同じ色のはそれぞれの同値
これはあくまでもイメージ図mrsekut.icon
じゃあ$ \equiv_mの方で、同じ領域内は全て多対一同値か？ 答えは No
関連
参考