L′ heißt reduzierbar auf L , falls es eine Funktion f:0,1∗→0,1∗ gibt mit
1.Für alle w aus 0,1∗ gilt: w ist in L′ genau dann, wenn in f(w) in L
2.Funktion f ist berechenbar, d.h., es gibt eine DTM Mf, die die Funktion f berechnet.
f heißt Reduktion von L′ auf L, geschrieben L′ ≤ L.