Příklad snížení z booleovského problému uspokojivosti na problém pokrytí vrcholů. Modré vrcholy tvoří kryt vrcholů, který odpovídá hodnotám pravdy.
V teorii vyčíslitelnosti a teorii výpočetní složitosti je redukce transformací jednoho problému na jiný. V závislosti na použité transformaci ji lze použít k definování tříd složitosti na souboru problémů.
Intuitivně, problém A je redukovatelný na problém B, pokud řešení B existují a dát řešení na A
vždy, když A má řešení.
Tudíž řešení A nemůže být těžší než řešení B. Napíšeme A ≤ B, obvykle s dolní index na ≤ označit typ snížení se používá.
Často se setkáváme s tím, že se snažíme vyřešit problém, který je podobný problému, který jsme již vyřešili. V těchto případech je často rychlým způsobem řešení nového problému přeměnit každou instanci nového problému na instance starého problému, vyřešit je pomocí našeho stávajícího řešení a pak pomocí nich získat naše konečné řešení. To je asi nejzřetelnější využití redukcí.
Další, jemnější použití je toto: předpokládejme, že máme problém, o kterém jsme prokázali, že je těžké ho vyřešit, a máme podobný nový problém. Mohli bychom mít podezření, že i tento problém je těžké vyřešit. Argumentujeme rozporem: předpokládejme, že nový problém je snadné vyřešit. Pak, pokud dokážeme, že každý případ starého problému lze snadno vyřešit tím, že jej přetvoříme na případy nového problému a vyřešíme ty, máme rozpor. To dokazuje, že nový problém je také těžký.
Velmi jednoduchý příklad redukce je od násobení ke kvadratuře. Předpokládejme, že vše, co víme, jak udělat, je sčítat, odečítat, brát čtverce a dělit dvěma. Můžeme použít tuto znalost, v kombinaci s následujícím vzorcem, abychom získali součin jakýchkoli dvou čísel:
Máme také redukci v opačném směru; samozřejmě, pokud můžeme vynásobit dvě čísla, můžeme umocnit číslo. Zdá se, že to znamená, že tyto dva problémy jsou stejně těžké. Tento druh redukce odpovídá Turingově redukci.
Redukce se však stane mnohem těžší, pokud přidáme omezení, že kvadratickou funkci můžeme použít pouze jednou a pouze na konci. V tomto případě, i když smíme použít všechny základní aritmetické operace, včetně násobení, neexistuje obecně žádná redukce, protože možná budeme muset vypočítat iracionální číslo jako z racionálních čísel. Pokud však půjdeme opačným směrem, určitě můžeme umocnit číslo jen jedním násobením, pouze na konci. Použitím této omezené formy redukce jsme ukázali nepřekvapivý výsledek, že násobení je obecně těžší než kvadratura. To odpovídá redukci mnoha jedniček.
Vzhledem k tomu, dvě podskupiny A a B z N a soubor funkcí F z N do N, který je uzavřen v rámci složení, A se nazývá redukovatelný do B pod F, pokud
Nechť S je podmnožinou P (N) a ≤ snížení, pak S se nazývá uzavřený pod ≤ pokud
A podmnožina A z N se nazývá těžké pro S, pokud
A podmnožina A z N se nazývá kompletní pro S, pokud A je těžké pro S a A je v S.
Redukce je předřazení, tedy reflexivní a tranzitivní vztah, na P(N)×P(N), kde P(N) je mocnina přirozených čísel.
Druhy a použití snížení
Jak je popsáno ve výše uvedeném příkladu, existují dva hlavní typy redukcí používaných ve výpočetní složitosti, redukce s mnoha jedničkami a Turingova redukce. Snižování s mnoha jedničkami mapuje instance jednoho problému k instancím jiného; Turingova redukce vypočítává řešení jednoho problému za předpokladu, že druhý problém je snadno řešitelný. Snižování s mnoha jedničkami je slabší než Turingova redukce. Slabší redukce jsou účinnější při oddělování problémů, ale mají menší výkon, takže redukce je těžší navrhnout.
Problém je kompletní pro třídu složitosti, pokud se každý problém ve třídě redukuje na tento problém, a je také ve třídě samotné. V tomto smyslu problém reprezentuje třídu, protože jakékoliv jeho řešení může být v kombinaci s redukcemi použito k řešení každého problému ve třídě.
Aby však byla redukce užitečná, musí být snadná. Například je docela možné redukovat obtížně řešitelný NP-úplný problém, jako je problém booleovské uspokojivosti, na triviální problém, jako je určení, zda se číslo rovná nule, tím, že redukční stroj vyřeší problém v exponenciálním čase a výstupní nule pouze v případě, že existuje řešení. Tím se ale moc nedosáhne, protože i když můžeme vyřešit nový problém, provedení redukce je stejně těžké jako vyřešení starého problému. Stejně tak redukce počítající nepočitatelnou funkci může redukovat nerozhodnutelný problém na řešitelný. Jak Michael Sipser upozorňuje v Úvodu k teorii výpočtu: „Redukce musí být snadná, vzhledem ke složitosti typických problémů ve třídě […] Pokud by samotná redukce byla obtížně vypočitatelná, snadné řešení úplného problému by nutně nepřineslo snadné řešení problémů redukujících se na ni.“
Proto je vhodné pojetí redukce závislé na třídě složitosti, která se zkoumá. Při studiu třídy složitosti NP a tvrdších tříd se používá mnohonásobná redukce polynomiálního času. Při definování tříd v hierarchii polynomů se používá Turingova redukce polynomiálního času. Při studiu tříd v rámci P, jako jsou NC a NL, se používá redukce log-space. Redukce se také používá v teorii vyčíslitelnosti, aby se ukázalo, zda problémy jsou nebo nejsou vůbec řešitelné stroji; v tomto případě jsou redukce omezeny pouze na vyčíslitelné funkce.
V případě optimalizačních (maximalizačních nebo minimalizačních) problémů často uvažujeme ve smyslu redukcí zachovávajících aproximaci. Předpokládejme, že máme dva optimalizační problémy takové, že instance jednoho problému mohou být mapovány na instance druhého, a to způsobem, že téměř optimální řešení instancí druhého problému mohou být transformována zpět, aby přinesla téměř optimální řešení prvního. Takto, pokud máme optimalizační algoritmus (nebo aproximační algoritmus), který najde téměř optimální (nebo optimální) řešení instancí problému B, a efektivní redukci zachovávající aproximaci z problému A na problém B, získáme složením optimalizační algoritmus, který přinese téměř optimální řešení instancí problému A. Redukce zachovávající aproximaci jsou často používány k prokázání tvrdosti výsledků aproximace: pokud je nějaký optimalizační problém A těžko aproximabilní (za nějakého předpokladu složitosti) v rámci faktoru lepšího než α pro některé α, a existuje β-aproximační zachování redukce z problému A do problému B, můžeme dojít k závěru, že problém B je těžké aproximovat v rámci faktoru α/β.
Následující příklad ukazuje, jak použít redukci z haltingového problému k prokázání, že jazyk je nerozhodnutelný. Předpokládejme, že H(M, w) je problém určení, zda daný Turingův stroj M zastavuje (přijetím nebo odmítnutím) na vstupním řetězci w. O tomto jazyce je známo, že je nerozhodnutelný. Předpokládejme, že E(M) je problém určení, zda jazyk, který daný Turingův stroj M přijímá, je prázdný (jinými slovy, zda M vůbec přijímá nějaké řetězce). Ukazujeme, že E je nerozhodnutelný redukcí z H.
Abychom získali rozpor, předpokládejme, že R je decider pro E. Použijeme to k vytvoření decideru S pro H (o kterém víme, že neexistuje). Při zadání vstupu M a w (Turingův stroj a nějaký vstupní řetězec) definujeme S(M, w) s následujícím chováním: S vytvoří Turingův stroj N, který přijímá pouze v případě, že vstupní řetězec pro N je w a M se zastaví na vstupu w, a jinak se nezastaví. decider S nyní může vyhodnotit R(N), aby zkontroloval, zda je jazyk přijatý N prázdný. Pokud R přijme N, pak je jazyk přijatý N prázdný, takže zejména M se nezastaví na vstupu w, takže S může odmítnout. Pokud R odmítne N, pak je jazyk přijatý N neprázdný, takže M se zastaví na vstupu w, takže S může přijmout. Tudíž, pokud bychom měli decider R pro E, byli bychom schopni vytvořit decider S pro zastavující se problém H(M, w) pro jakýkoliv stroj M a vstup w. Protože víme, že takové S nemůže existovat, vyplývá z toho, že jazyk E je také nerozhodnutelný.