Many-One-Reduzierbarkeit

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.