Satz Falls B in P und A poly reduzierbar auf B dann A in P
Einfache Sprache
Def. Satz Falls B in P und A poly reduzierbar auf B dann A in P
Aus $A\leq_\mathrm{P} B$ und $B\in\mathbf P$ folgt $A\in\mathbf P$.
Beweis: Sei $\mathcal M$ eine TM (oder Algorithmus) der $B$ in deterministisch polynomielle Zeit entscheidet. Sei $f$ eine Polynomialzeitreduktion von $A$ auf $B$. Dann funktioniert eine TM $\mathcal N$, die in deterministisch polynomielle Zeit $A$ entscheidet, wie folgt für die Eingabe $w$:
- Berechne $f(w)$.
- Lasse $\mathcal M$ auf der Eingabe $f(w)$ laufen und gebe aus was $\mathcal M$ ausgibt.
Nach der Definition von $f$ als Polynomialzeitreduktion von $A$ nach $B$ gilt das $w\in A$ genau dann wenn $f(w)\in B$. Also akzeptiert $\mathcal M$ $f(w)$ g.d.w. $w\in A$. Außerdem läuft $\mathcal N$ in deterministisch polynomielle Zeit, da bei TMs in P sind und die Komposition von zwei Polynomen ist ein Polynom.