Polynomiální redukce

Polynom redukce je nástroj pro teoretické informatiky , konkrétně na teorii složitosti . Jedná se o zvláštní třídu redukcí, která je obzvláště důležitá, zejména pro problém P = NP .

Definice

V rámci formálních jazyků pro rozhodovací problémy říkáme, že jazyk je redukovatelný v polynomiálním čase na jazyk (označený ), pokud v polynomiálním čase existuje vypočítatelná funkce pro všechny , pokud a pouze pokud . Voláme funkci na funkci redukce a polynomiální algoritmus, který počítá se nazývá algoritmus redukce . L1{\ displaystyle L_ {1} \!}L2{\ displaystyle L_ {2} \!}L1≤PL2{\ displaystyle L_ {1} \ leq _ {P} L_ {2}} F:{0,1}∗→{0,1}∗{\ displaystyle f: \ left \ {0,1 \ right \} ^ {*} \ rightarrow \ left \ {0,1 \ right \} ^ {*}}X∈{0,1}∗{\ displaystyle x \ in \ left \ {0,1 \ right \} ^ {*}}X∈L1{\ displaystyle x \ v L_ {1}}F(X)∈L2{\ displaystyle f (x) \ v L_ {2}}F{\ displaystyle f \!}F{\ displaystyle f \!}

Vztah mezi rozhodovacím problémem a jeho přidruženým jazykem

Kódování

Buď problém s rozhodnutím . Případy tohoto problému jsou abstraktní objekty v tom smyslu, že jejich definice je čistě matematická. Aby bylo možné implementovat tento problém, musí být ale zastoupeny ve formě srozumitelné programu. Zde přichází pojem kódování . Definujeme funkci kódování rozhodovacího problému jako injektivní aplikaci, která se přidruží k sadě abstraktních instancí prvku . Když tedy programátor kóduje problém, proměnné představující instance problému jsou přeloženy ( překladačem v případě statických jazyků, tlumočníkem v případě dynamických jazyků) do binárního jazyka. Kódování je tedy způsob přechodu od abstraktního problému ke konkrétnímu problému. Ve skutečnosti, pokud řešením rozhodnutí problém abstraktní Například je -li řešení instance konkrétní problém je . Existuje však malý problém: je možné, že prvky typu neodpovídají žádné instanci problému (tj. Nemají předchůdce ). Pro usnadnění budeme předpokládat, že jakýkoli takový řetězec je obrázek 0. Q{\ displaystyle Q \!}vs.{\ displaystyle c \!}Q{\ displaystyle Q \!}Q{\ displaystyle Q \!}{0,1}∗{\ displaystyle \ left \ {0,1 \ right \} ^ {*}}i∈Já{\ displaystyle i \ in I}Q(i)∈{0,1}{\ displaystyle Q (i) \ v \ vlevo \ {0,1 \ vpravo \}}vs.(i)∈{0,1}∗{\ displaystyle c (i) \ v \ vlevo \ {0,1 \ vpravo \} ^ {*}}Q(i){\ displaystyle Q (i) \!}{0,1}∗{\ displaystyle \ left \ {0,1 \ right \} ^ {*}}

Vztah mezi rozhodovacími problémy a algoritmy, které je řeší

• Algoritmus přijímá řetězec, pokud je daný vstup ukončenNA{\ displaystyle A \!} X∈{0,1}∗{\ displaystyle x \ in \ left \ {0,1 \ right \} ^ {*}}X{\ displaystyle x \!}NA(X)=1{\ displaystyle A (x) = 1 \!}
• Algoritmus odmítne řetězec, pokud .NA{\ displaystyle A \!} X{\ displaystyle x \!}NA(X)=0{\ displaystyle A (x) = 0 \!}

Jazyk akceptován

• Jazyk přijímaný algoritmem je sada řetězců přijímaných algoritmem, tj .NA{\ displaystyle A \!}L={X∈{0,1}∗:NA(X)=1}{\ displaystyle L = \ left \ {x \ in \ left \ {0,1 \ right \} ^ {*}: A (x) = 1 \ right \}}

Jazyk rozhodl

• Jazyk je rozhodnuto algoritmem pokud existuje řetězec bitů, které nepatří k odmítnut .L{\ displaystyle L \!}NA{\ displaystyle A \!}L{\ displaystyle L \!}NA{\ displaystyle A \!}

Třída a jazyk složitosti

Můžeme neformálně definovat třídu složitosti jako sadu jazyků, jejichž členství je určeno mírou složitosti algoritmu, který určuje, zda daný řetězec patří do jazyka . Třídu složitosti lze tedy definovat jako množinu jazyků, o nichž rozhoduje polynomiální časový algoritmus. X{\ displaystyle x \!}L{\ displaystyle L \!}P{\ displaystyle P \!}{0,1}∗{\ displaystyle \ left \ {0,1 \ right \} ^ {*}}

Užitečnost

Pojem redukce polynomiálního času se používá v rámci teorie složitosti algoritmů k umožnění klasifikace problémů. Skutečně umožňuje ukázat formálním způsobem a v polynomiálním čase, že problém je přinejmenším stejně obtížný jako jiný: pokud pak není obtížnější než , nebo řečeno teoretičtěji: a má stejnou třídu složitosti . L1≤PL2{\ displaystyle L_ {1} \ leq _ {P} L_ {2}}L1{\ displaystyle L_ {1} \!}L2{\ displaystyle L_ {2} \!}L1{\ displaystyle L_ {1} \!}L2{\ displaystyle L_ {2} \!}

Příklady redukce

• Kryté na dílčí součet
• Klikněte na 3-SAT
• SAT až 3-SAT
• Dílčí součet na SAT
• 3-SAT kliknout
• 3-SAT na vrcholový kryt

Poznámky a odkazy

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">