Redukcja (teoria złożoności)

Redukcja – termin teorii złożoności obejmujący różnorodne metody przekształcania danego problemu w inny, w pewien sposób co najwyżej tak samo trudny, w celu klasyfikacji problemów ze względu na pewną ich cechę: rozpoznawalność, rozstrzygalność, czy przynależność do jednej z wielu klas złożoności.

Poszczególne redukcje, często ze sobą powiązane, noszą nazwiska badaczy teorii złożoności, m.in. redukcja Turinga, redukcja Karpa, redukcja Cooka, redukcja Levina.