Příklad redukce z problému splnitelnosti na problém pokrytí vrcholů. Modré vrcholy tvoří vrcholový obal, který odpovídá pravdivostním hodnotám.
V teorii vypočitatelnosti a teorii výpočetní složitosti je redukce transformací jednoho problému na jiný problém. V závislosti na použité transformaci ji lze použít k definování tříd složitosti na množině problémů.
Intuitivně je problém A redukovatelný na problém B, pokud existují řešení B a dávají řešení A.
kdykoli má A řešení.
Řešení A tedy nemůže být těžší než řešení B. Zapisujeme A ≤ B, obvykle s indexem ≤, který označuje typ použité redukce.
Často se stává, ž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 transformovat 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 je použít k získání našeho konečného řešení. To je asi nejzřetelnější použití redukcí.
Další, jemnější použití je následující: předpokládejme, že máme problém, u kterého jsme prokázali, že je těžko řešitelný, a máme podobný nový problém. Můžeme mít podezření, že i ten je obtížně řešitelný. Argumentujeme rozporem: předpokládejme, že nový problém je snadno řešitelný. Pak, pokud dokážeme, že každou instanci starého problému lze snadno vyřešit tak, že ji převedeme na instance nového problému a ty vyřešíme, máme kontradikci. Tím zjistíme, že nový problém je také těžký.
Velmi jednoduchým příkladem redukce je přechod z násobení na odmocňování. Předpokládejme, že jediné, co umíme, je sčítat, odčítat, brát čtverce a dělit dvěma. Tuto znalost můžeme v kombinaci s následujícím vzorcem použít k získání součinu libovolných dvou čísel:
Máme také redukci v opačném směru; je zřejmé, že pokud umíme násobit dvě čísla, můžeme číslo odmocnit. Z toho se zdá vyplývat, že tyto dva problémy jsou stejně těžké. Tento druh redukce odpovídá Turingově redukci.
Redukce se však stává mnohem obtížnější, pokud přidáme omezení, že funkci odmocňování můžeme použít pouze jednou, a to pouze na konci. V takovém případě, i když smíme použít všechny základní aritmetické operace včetně násobení, žádná redukce obecně neexistuje, protože můžeme muset počítat iracionální číslo jako z racionálních čísel. Půjdeme-li však opačným směrem, jistě můžeme číslo odmocnit pouze jedním násobením, a to až na konci. Pomocí této omezené formy redukce jsme ukázali nepřekvapivý výsledek, že násobení je obecně těžší než odmocňování. To odpovídá redukci na mnoho jedniček.
Jsou-li dány dvě podmnožiny A a B z N a množina funkcí F z N do N, která je uzavřená při kompozici, nazývá se A redukovatelná na B při F, jestliže
Nechť S je podmnožina P(N) a ≤ je redukce, pak se S nazývá uzavřená pod ≤, jestliže
Podmnožina A z N se nazývá těžká pro S, jestliže
Podmnožina A z N se nazývá úplná pro S, jestliže A je pro S těžká a A je v S.
Redukce je preordering, tj. reflexivní a tranzitivní relace, na P(N)×P(N), kde P(N) je mocninná množina přirozených čísel.
Typy a použití redukcí
Jak bylo popsáno v příkladu výše, ve výpočetní složitosti se používají dva hlavní typy redukcí, a to mnohojediná redukce a Turingova redukce. Mnohojediná redukce mapuje instance jednoho problému na instance jiného; Turingova redukce počítá řešení jednoho problému za předpokladu, že druhý problém je snadno řešitelný. Mnohojediná redukce je slabší než Turingova redukce. Slabší redukce jsou efektivnější při rozdělování problémů, ale mají menší sílu, takže se redukce hůře navrhují.
Problém je pro třídu složitosti úplný, pokud se na něj redukuje každý problém v této třídě a pokud je také v samotné třídě. V tomto smyslu problém reprezentuje třídu, protože každé jeho řešení lze v kombinaci s redukcemi použít k řešení každého problému ve třídě.
Aby však bylo snížení užitečné, musí být snadné. Například je docela dobře možné redukovat obtížně řešitelný NP-úplný problém, jako je problém booleovské splnitelnosti, na triviální problém, jako je určení, zda se číslo rovná nule, a to tak, že redukční stroj řeší problém v exponenciálním čase a výstupem je nula pouze v případě, že existuje řešení. Tím však mnoho nedosáhneme, protože i když můžeme vyřešit nový problém, provedení redukce je stejně obtížné jako řešení starého problému. Podobně redukce počítající s nepočitatelnou funkcí může redukovat nerozhodnutelný problém na rozhodnutelný. Jak upozorňuje Michael Sipser v knize Introduction to the Theory of Computation: Kdyby byla redukce sama o sobě obtížně spočitatelná, nemuselo by snadné řešení kompletního problému nutně přinést snadné řešení problémů, které se na ni redukují.“ (Sipsers, J.: „Redukce musí být snadná vzhledem ke složitosti typických problémů v dané třídě […].
Vhodný pojem redukce proto závisí na studované třídě složitosti. Při studiu třídy složitosti NP a těžších tříd se používá redukce v polynomiálním čase na mnoho jedniček. Při definování tříd v polynomiální hierarchii se používá Turingova redukce v polynomiálním čase. Při studiu tříd v rámci P, jako jsou NC a NL, se používá logaritmická redukce. Redukce se také používá v teorii spočitatelnosti, aby se ukázalo, zda problémy jsou nebo nejsou vůbec řešitelné stroji; v tomto případě se redukce omezují pouze na spočitatelné funkce.
V případě optimalizačních (maximalizačních nebo minimalizačních) problémů často uvažujeme v termínech redukcí zachovávajících aproximaci. Předpokládejme, že máme dva takové optimalizační problémy, že instance jednoho problému lze přenést na instance druhého tak, že téměř optimální řešení instancí druhého problému lze transformovat zpět tak, aby vzniklo téměř optimální řešení prvního problému. Máme-li tedy optimalizační algoritmus (nebo aproximační algoritmus), který nachází téměř optimální (nebo optimální) řešení instancí problému B, a účinnou redukci zachovávající aproximaci z problému A na problém B, získáme složením optimalizační algoritmus, který dává téměř optimální řešení instancí problému A. Redukce zachovávající aproximaci se často používají k důkazu tvrdosti aproximačních výsledků: je-li nějaký optimalizační problém A obtížně aproximovatelný (za nějakého předpokladu složitosti) v rámci faktoru lepšího než α pro nějaké α a existuje-li redukce zachovávající aproximaci β z problému A na problém B, můžeme usoudit, že problém B je obtížně aproximovatelný v rámci faktoru α/β.
Následující příklad ukazuje, jak pomocí redukce z problému zastavení dokázat, že jazyk je nerozhodnutelný. Předpokládejme, že H(M, w) je problém určení, zda se daný Turingův stroj M zastaví (přijetím nebo odmítnutím) na vstupním řetězci w. O tomto jazyku 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 akceptuje, je prázdný (jinými slovy, zda M vůbec akceptuje nějaké řetězce). Ukážeme, že E je nerozhodnutelný redukcí z H.
Abychom získali kontradikci, předpokládejme, že R je decimátor pro E. Toho využijeme k vytvoření decimátoru S pro H (o kterém víme, že neexistuje). Při daných vstupech M a w (Turingův stroj a nějaký vstupní řetězec) definujte S(M, w) s následujícím chováním: S vytvoří Turingův stroj N, který akceptuje pouze tehdy, je-li vstupní řetězec do N w a M se zastaví na vstupu w, a jinak se nezastaví. Rozhodovací stroj S nyní může vyhodnotit R(N), aby ověřil, zda jazyk akceptovaný strojem N je prázdný. Pokud R akceptuje N, pak je jazyk akceptovaný N prázdný, takže zejména M se na vstupu w nezastaví, takže S může odmítnout. Pokud R odmítá N, pak jazyk přijatý N není prázdný, takže M se na vstupu w zastaví, takže S může přijmout. Kdybychom tedy měli rozhodovatel R pro E, byli bychom schopni vytvořit rozhodovatel S pro problém zastavení H(M, w) pro libovolný 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ý.