Eigenschaft eines Entscheidungsproblems.

Ein Entscheidungsproblem A ⊆ ℕ₀ ist auf ein Entscheidungsproblem B ⊆ ℕ₀ (many-one-)reduzierbar, falls es eine total berechenbare Funktion f : ℕ₀ → ℕ₀ gibt mit f⁻¹(B) = A. (Schreibweise: A ≤_mB).

Sofern A ≤_mB gilt, so überträgt sich die Unentscheidbarkeit von A auf B. Die Bezeichnung „many-one“ erklärt sich dadurch, daß die Funktion f (im Unterschied zur one-one-Reduzierbarkeit) nicht injektiv zu sein braucht.