Satz poly Reduktion und P dann P

Einfache Sprache

Def. Satz poly Reduktion und P dann P

Sei $A,B$ Sprachen. Wenn $A$ polynomial reduzierbar auf $B$ ist und $B$ in P, dann ist $A$ auch in P. Also

$$A\leq_\mathrm{p} B \land B\in \mathbf{P}\implies A\in\mathbf{P}\;.$$

Idee:

Beweis: Sei $M$ ein Polynomialzeit Algorithmus der $B$ entscheidet und $f$ eine Polynomialzeitreduktion die $A$ auf $B$ reduziert. Dann funktioniert der Polynomialzeit Algorithmus der $A$ entscheidet für die Eingabe $w$ wie folgt:

1. Berechne $f(w)$.
2. Lass $M$ mit $f(w)$ als Eingabe laufen und gebe aus was $M$ ausgibt.

Nach der Definition von $f$ gilt $w\in A$ gdw. $f(w)\in B$. Deswegen akzeptiert $M$ $f(w)$ gdw. $w\in A$. Zudem läuft $M$ in Polynomialzeit, weil bei Schritte von $M$ jeweils in Polynomialzeit laufen. Die Komposition von zwei Polynomialzeiten ist weider rum eine Polynomialzeit.