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.).
🔥 Top keywords: Wikipedia:Strona głównaMistrzostwa Europy w Piłce Nożnej 2024Specjalna:SzukajWikipedia:O WikipediiMichał ProbierzMistrzostwa Europy w Piłce Nożnej 2020Kylian MbappéMistrzostwa Europy w piłce nożnejMistrzostwa Świata w Piłce Nożnej 2022Antoine GriezmannNicola ZalewskiMistrzostwa świata w piłce nożnej mężczyznReprezentacja Francji w piłce nożnej mężczyznDzień OjcaTaras RomanczukRomelu LukakuMistrzostwa Europy w Piłce Nożnej 2016Reprezentacja Polski w piłce nożnej mężczyznAdam BuksaZofia Noceti-KlepackaPolskaDidier DeschampsRobert LewandowskiMistrzostwa Świata w Piłce Nożnej 2026FentanylMistrzostwa Europy w Piłce Nożnej 2028N’Golo KantéOndrej DudaPałac Stolbergów we WrocławiuSłowacjaGheorghe HagiMistrzostwa Europy w Piłce Nożnej 2020/FinałCristiano RonaldoReprezentacja Rumunii w piłce nożnej mężczyznMistrzostwa Europy w Piłce Nożnej 2012Tadeusz GapińskiMistrzostwa Europy w Piłce Nożnej 2024 (eliminacje)Olivier GiroudDawid Podsiadło