多対一還元
二つの集合 A , B ⊆ N {\displaystyle A,B\subseteq \mathbb {N} } があるとする。何らかの全体計算可能関数 f {\displaystyle f} が存在して A = f − 1 [ B ] {\displaystyle A=f^{-1}[B]} であるとき、 A {\displaystyle A} は B {\displaystyle B} に多対一還元可能であると言い、次のように書く。
A ≤ m B . {\displaystyle A\leq _{m}B.}
これに加えて f {\displaystyle f} が単射である場合、 A {\displaystyle A} は B {\displaystyle B} に1-還元可能であると言い、次のように書く。
A ≤ 1 B . {\displaystyle A\leq _{1}B.}
帰納的可算集合 B が存在し、全ての帰納的可算集合 A が B に m-還元可能であるとき、B は多対一完全またはm-完全であると言う。