Reduktionslemma (i) Wenn Q∈PQ \in \mathcal{P}Q∈P und PPP polynomiell reduzierbar auf QQQ ist, dann ist P∈PP \in \mathcal{P}P∈P. (ii) Wenn P∈NPCP \in \mathcal{NPC}P∈NPC und P polynomiell reduzierbar auf QQQ ist, dann ist Q∈NPCQ \in \mathcal{NPC}Q∈NPC.