Redukce (složitost)
V teorii vypočítatelnosti a složitosti je redukce algoritmus, který transformuje instanci algoritmického problému na jednu (nebo více) instancí jiného problému. Pokud dojde k takové redukci z problému A na problém B, říkáme, že problém A se redukuje na problém B. V tomto případě je problém B obtížnější než problém A, protože problém můžeme vyřešit aplikací redukce a algoritmus pro problémovou B. pak jsme psát o ≤ B .
Existují dvě použití redukcí.
- Ukažte, že problém je ze své podstaty obtížný. Například pomocí redukce ukážeme, že problémy jsou nerozhodnutelné : pak ukážeme, že problém je tak algoritmicky obtížný, že o něm nerozhoduje žádný algoritmus . Tyto polynomiální redukce jsou použity k prokázání, že problémy jsou NP-těžký. Obecněji se redukcemi prokazuje, že problém patří mezi nejobtížnější třídy složitosti .
- Ukažte, že problém lze snadno vyřešit algoritmicky. Například, pokud ≤ B s ≤ snížení polynomiálním čase, a B patří do P , pak je také v P .
Úvodní příklad
Zvažte dva problémy: problém M vynásobení dvou celých čísel a problém C umocnění celého čísla na druhou. C. Problém je jednodušší, než problém M. Ve skutečnosti, pokud můžeme dělat násobení, můžete zvýšit počet kvadrát vynásobením sám, takže C ≤ M . Redukce C v M je : transformujeme celé číslo na druhou na data dvou stejných celých čísel (x, x), která se mají vynásobit.
Je zajímavé, že můžeme také ukázat, že M se redukuje na C ( M ≤ C ). Opravdu, díky vzorci:
vidíme, že můžeme vypočítat součin a a b výpočtem tří čtvercových výšek. Oba problémy jsou tedy stejně obtížné (lze je navzájem redukovat).
Definice
Následující definice zahrnují celá čísla, protože instance problémů jsou kódovány v ℕ.
Vzhledem k tomu, dvě sady přirozených celých čísel A a B , a sadu funkcí F od ℕ do ℕ, uzavřené složením, se říká , že A je redukovatelný na B o F, pokud:
Napsali jsme .
Nechť S je podmnožinou P (ℕ) a ≤ redukcí, pak se říká, že S je uzavřeno ≤, pokud
O podmnožině A z ℕ se říká, že je pro S obtížná , pokud
Konečně podmnožina z N je, že plně pro S -li je obtížné, O a patří S .
Příklady
Chcete-li dokázat, že problém je NP-úplný , lze snížit známý problém NP-kompletní (například SAT problém ) na tento problém pomocí polynomiální redukce .
V oblasti vypočítatelnosti lze například dokázat Riceovu větu snížením problému zastavení .
Druhy redukce
Existuje několik typů redukce.
- Turingova redukce
- Cookova sleva
- Polynomiální zkrácení času
- Redukce v logaritmickém prostoru
- Snížení první objednávky
- Levinovy redukce jsou polynomiální funkce, které se transformují do několika certifikátů
- Snížení polynomiálního času tabulkou pravdy: problém A se sníží v polynomiálním čase tabulkou pravdy, pokud můžeme rozhodnout, zda x patří k A, předpočítáním několika otázek příslušnosti slov k B a popsáním booleovského vzorce na odpovědi na jeho otázky rozhodnout, zda x patří do A. Přesněji, Buss a Hay zavádějí varianty podle toho, zda je booleovský vzorec reprezentován jeho syntaktickým stromem, obvodem nebo pravdivostní tabulkou.
- Redukce, které zachovají aproximační faktor mezi optimalizačním problémem v oblasti aproximačních algoritmů
Podívejte se také
Poznámky a odkazy
- Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest a Clifford Stein , Úvod do algoritmiky , Dunod ,2002[ detail vydání ] kapitola 34, NP-dokončení
- (en) Immerman, popisná složitost
- (en) Arora, Barak, Výpočetní složitost - moderní přístup , str. 55
- (in) „ Srovnání polynomiálních časových redukcí “ , Theoretical Computer Science , sv. 1, n O 21 st 12. 1975, str. 103–123 ( ISSN 0304-3975 , DOI 10.1016 / 0304-3975 (75) 90016-X , číst online , přistupováno 18. prosince 2018 )
- Samuel R. Buss a Louise Hay , „ Redukovatelnost stolu pravdy na SAT “, Inf. Comput. , sv. 91, n o 1,Březen 1991, str. 86–102 ( ISSN 0890-5401 , DOI 10.1016 / 0890-5401 (91) 90075-D , číst online , přístup k 18. prosinci 2018 )
- (en) Vijay V. Vazirani , Aproximační algoritmy , Springer-Verlag,2003( ISBN 978-3-540-65367-7 , číst online ) , část A.3.1, s. 348