##  [Many-One-Reduzierbarkeit](/de/node/60169) 

  ##  [Many-One-Reduzierbarkeit](https://mathlogic.quantumdictionary.io/de/node/60170) 

  

 [![Mathematics & Logic Dictionary](/sites/default/files/styles/large/public/2026-01/Mathematics%20%26%20Logic.png.webp?itok=UhtTRPnp)](/topic-specific-dictionaries/natural-formal-sciences/mathematics-logic)

- Natural & Formal Sciences -

**Mathematics & Logic Dictionary**

 







 

 

 

 



 

 

 

 

Definition

Eine Berechenbarkeitsrelation zwischen Entscheidungsproblemen A und B: A ist many-one-reduzierbar auf B, wenn es eine berechenbare Funktion f gibt, die Instanzen x auf f(x) abbildet, so dass x in A genau dann ist, wenn f(x) in B ist. Die Reduktion ist einzelaufrufend und nicht adaptiv.