多対一還元
A と B をそれぞれアルファベットの集合 Σ と Γの上で書かれた形式言語だとしよう。A から B への多対一還元とは、次の性質を満たすような全体計算可能関数 f : Σ → Γ を指す。性質:「個々の単語 w が A の中にある必要十分条件が、『f(w) が B の中にあること』(即ち、 A = f − 1 ( B ) {\displaystyle A=f^{-1}(B)} )である」。
もしそのような関数 f が存在するなら、A は B に多対一還元可能またはm-還元可能であると言い、次のように書く。
A ≤ m B . {\displaystyle A\leq _{m}B.}
もし単射な多対一還元があるなら、A は B に1-還元可能または一対一還元可能であると言い、次のように書く。
A ≤ 1 B . {\displaystyle A\leq _{1}B.}