Polynomiální redukovatelnost

Říká se, že jakýkoli jazyk je Karpově redukovatelný na jazyk , pokud existuje funkce , kterou lze vypočítat v polynomiálním čase, kde F(x) patří , pokud x patří do . Jazyk se nazývá NP-tvrdý, pokud je na něj redukovatelný jakýkoli jazyk třídy NP, a nazývá se NP-úplný, pokud je NP-tvrdý a je sám o sobě redukovatelný na třídu NP. Pokud existuje algoritmus, který řeší NP-úplný problém v polynomiálním čase, pak všechny NP-problémy patří do třídy P. $L_{1}$ $L_{2}$ $F\colon \Sigma ^{*}\mapsto \Sigma ^{*}$ $L_{2}$ $L_{1}$

Zvažte dva jazyky a přes abecedy a . Karpova redukce na je funkce, kterou lze vypočítat v polynomiálním čase tak, že . Neformálně tedy jazyk není „o nic těžší“ než jazyk . $L_{1}$ $L_{2}$ $\Sigma$ $\Gamma$ $L_{1}$ $L_{2}$ $f\colon \Sigma ^{*}\mapsto \Gamma ^{*}$ $\forall x(x\v L_{1}\Šipka doleva doprava f(x)\v L_{2})$ $L_{1}$ $L_{2}$

Pokud taková funkce existuje, říkáme, že je to Karp redukovatelná na a zapisovatelná $F$ $L_{1}$ $L_{2}$

L_{1}\leqslant _{K}L_{2}.

Všimněte si, že Karp redukce je speciální případ Cook redukce . V anglických zdrojích se můžete setkat i s názvem en:many-one reduction .

Jazyková třída PSPACE je sada jazyků povolených deterministickým Turingovým strojem s polynomiálním prostorovým omezením.

Jazyková třída NPSPACE je sada jazyků povolených nedeterministickým Turingovým strojem s polynomiálním prostorovým omezením.

Tranzitivita

Hlavní vlastností Karp redukce je tranzitivita. Pokud jsou jazyky reprezentovány jako symboly, lze to považovat za matematickou operaci: Α>Β, Β>Ε → Α>Ε.

Viz také

Pojem informace. Seznam.

Odkazy

Kurz "Úvod do teorie strukturní složitosti"
Hopkfroft J., Motwani R., Ulman J. Úvod do teorie automatů, jazyků a počítání, 2. vyd.: Per. z angličtiny. - M.: Williams Publishing House, 2002.
M. N. Vyaly , Složitost výpočetních problémů