Polynomialzeitreduktion

Einfache Sprache

Hier wird das Konzept der Reduktion verfeinert.

Def. Polynomialzeitreduktion

Eine Sprache $A$ ist polynomial reduzierbar zu einer Sprache $B$, geschrieben $A\leq_\mathrm{p} B$ fall es eine Polynomialzeit 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 Polynomialzeitreduktion von $A$ nach $B$ genannt.

Polynomielle Transformation

Def. polynomielle Transformation

Eine Transformation heißt polynomielle Transformation, wenn es ein Polynom $p$ und einen Algorithmus $A$ git, der f.a. $w\in\Sigma_1^*$ die Ausgabe $f(w)$ der Länge $\leq p(|w|)$ in polynomieller Zeit $T_A(w)\leq p(|w|)$ berechnet. Dann heißt $L_1$ polynomiell reduzierbar auf $L_2$. Als Notation verwenden wir $L_1 \leq L_2$.