Miféle ötlet ez a csökkentés? Az előző kérdés alapján írj egy szövegkörnyezetet, amely tartalmazza a választ. Lehet 1 - 20 mondat. A szövegkörnyezet:
Sok komplexitási osztályt a redukció fogalmának felhasználásával határoznak meg. A redukció egy probléma átalakulása egy másik problémává. Megragadja a nem hivatalos fogalmat, hogy egy probléma legalább olyan nehéz, mint egy másik probléma. Például, ha egy X probléma megoldható egy Y algoritmus használatával, akkor az X nem nehezebb, mint az Y, és azt mondjuk, hogy az X Y-re redukálódik. Sokféle redukció létezik, a redukció módszerén alapulva, mint például a Cook redukció, a Karp redukció és a Levin redukció, és a redukciók komplexitásának határértéke, mint például a polinomiális idő redukció vagy a log-tér redukció.