# Notizen 6

Bei der Reduktion wird ein Problem einer niedrigereren oder gleichen Klasse auf ein anderes reduziert.

[Berechenbar](https://de.wikipedia.org/wiki/Berechenbarkeit): Terminiert bei allen Eingaben

Dafür brauch man eine Turing-berechenbare Reduktionsfunktion $f$.

Es gilt:

$$w\in L_1\leqslant f(w)\in L_2$$

Dabei gilt:
1. Ist $L_1$ nicht entscheidbar/erkennbar, dann ist $L_2$ nicht entscheidbar/erkennbar.
2. Ist $L_2$ entscheidbar/erkennbar, dann ist $L_1$ entscheidbar/erkennbar.

Also hat $L_1$ stets mehr oder gleich viele Eigenschaften(Entscheidbar, Erkennbar, Co-Erkennbar) als $L_2$.

Man könnte also auch sagen:

$$|L_1|_{\text{Eigenschaften}}\geqslant|L_2|_{\text{Eigenschaften}}$$

Und das sieht fast so aus wie:

$$L_1\leqslant L_2$$

Dabei ist aber das Verhältnis-Zeichen falsch.

$$w\rightarrow L_1\leqslant w\rightarrow (f\rightarrow L_2)$$