Redukcja (teoria złożoności)
Z Wikipedii, wolnej encyklopedii
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.
- Michael Sipser: Introduction to the Theory of Computation. Wyd. 3. Cengage Learning, 2012. ISBN 978-1133187790. (ang.).
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
