Lexikon der Mathematik: many-one-Reduzierbarkeit
Eigenschaft eines Entscheidungsproblems.
Ein Entscheidungsproblem A ⊆ ℕ0 ist auf ein Entscheidungsproblem B ⊆ ℕ0 (many-one-)reduzierbar, falls es eine total berechenbare Funktion f : ℕ0 → ℕ0 gibt mit f−1(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.
Copyright Springer Verlag GmbH Deutschland 2017
Schreiben Sie uns!