Reduktion

Def. Reduktion

Eine Sprache $A$ ist reduzierbar zu einer Sprache $B$, geschrieben $A\leq_\mathrm{m} B$ fall es eine Berechenbare Funktion $f:\Sigma^*\to\Sigma^*$ existiert so, dass für alle $w$ gilt

$$w\in A\iff f(w)\in B\;.$$

Die Funktion $f$ wird auch Reduktion von $A$ nach $B$ genannt.

Alte Definition

Def. Transformation

Es sei $L_1\subseteq\Sigma^*_1$,$L_2\subseteq\Sigma^*_2$ zwei Sprachen.

Eine Funktion $f:\Sigma_1^*\to\Sigma_2^*$ mit der Eigenschaft

$$w\in L_1 \Leftrightarrow f(w)\in L_2\quad \forall w\in\Sigma_1^*$$

heißt Transformation von $L_1$ auf $L_2$.