Reduktionslemma

(i) Wenn $Q\in \mathcal{P}$ und $P$ polynomiell reduzierbar auf $Q$ ist, dann ist $P\in \mathcal{P}$.

(ii) Wenn $P\in \mathcal{NP}\mathcal{C}$ und P polynomiell reduzierbar auf $Q$ ist, dann ist $Q\in \mathcal{NP}\mathcal{C}$.