Redukcja (teoria złożoności)
Z Wikipedii, wolnej encyclopedia
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.