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.

Bibliografia

• Michael Sipser: Introduction to the Theory of Computation. Wyd. 3. Cengage Learning, 2012. ISBN 978-1133187790. (ang.).brak strony w książce