Karp還元とも言う

チューリング還元の特殊版

チューリング還元よりも、強い主張

厳しい、範囲が狭い主張

Emil Leon Postが1944年に導入

定義

自然数の集合\alpha,\betaに対して以下の条件が成り立つとき\alpha\le_m\betaと書く

計算可能1変数全域関数fが存在して、任意の自然数xに対して以下が成り立つ

x\in\alpha \iff f(x)\in\beta

このfのことを帰着関数と言う

fは逆写像も、単射、全射であるかどうかも定義されていないことに注意

なので下図のようになることもありうる

\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とイコールになるとは限らない

定理

\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}}

補足

\equiv_mは多対一同値

\equiv_Tはチューリング同値

チューリング次数と多対一次数のきめ細やさのイメージ

下図はイメージであって厳密な何かではない

同じ集合をチューリング同値同士と多対一同値同士で分けたとき、後者の方が細かく分類される

定理

\betaが\Sigma_n集合で\alpha\le_m\betaならば、\alphaも\Sigma_n集合である

従って、\betaが\Sigma_n集合で\alpha\equiv_m\betaならば、\alphaも\Sigma_n集合である

\le_mよりも\equiv_mの方が厳しいので、前者で成り立つなら後者でも成り立つ

\Sigma_nを\Pi_nに換えても成り立つ

多対一同値は算術的階層の各領域に閉じている

一方でチューリング同値は閉じているとは限らない

e.g. haltPairは②に属し、その補集合は③に属し、これらはチューリング同値

同じ色のはそれぞれの同値

これはあくまでもイメージ図

じゃあ\equiv_mの方で、同じ領域内は全て多対一同値か？

答えは No

ref ポストの問題

関連

参考