Direkt zum Inhalt

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: AmB).

Sofern AmB 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.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos