Doplňkové (složitost)
V teorii složitosti (pole teoretické informatiky ), mluvíme o doplňku třídy C, označeném co-C nebo coC, abychom označili sadu jazyků doplňujících jazyky této třídy. Tento operátor vede k tomu, že nové třídy považuje za co-NP , doplněk NP .
Formální definice
Doplňkové k jazyku
Zvažte jazyk abecedy a sadu slov . Pak doplněk , je zde uvedeno . Všimli jsme si zejména toho, že doplněk je .
L{\ displaystyle L}
Σ{\ displaystyle \ Sigma}
Σ∗{\ displaystyle \ Sigma ^ {*}}
Σ{\ displaystyle \ Sigma}
L{\ displaystyle L}
L¯{\ displaystyle {\ bar {L}}}
Σ∗∖L{\ displaystyle \ Sigma ^ {*} \ setminus L}
L¯{\ displaystyle {\ bar {L}}}
L{\ displaystyle L}![L](https://wikimedia.org/api/rest_v1/media/math/render/svg/103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8)
Doplňuje jazykovou třídu
Buď C třída, pak jeho komplementární ko-C: .
vs.Ó-VS={U⊆Σ∗|U¯⊆VS}{\ displaystyle co {\ text {-}} C = \ {U \ subseteq \ Sigma ^ {*} | {\ bar {U}} \ subseteq C \}}![{\ displaystyle co {\ text {-}} C = \ {U \ subseteq \ Sigma ^ {*} | {\ bar {U}} \ subseteq C \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b1d5225728f28bb714ea05b4b157be3d7dc35069)
Pokud jde o Turingovy stroje
Vezmeme-li pohled na Turingovy stroje a problémy, problém doplňkového rozhodování je ten, kde jsme pro odpověď na otázku obrátili „ano“ a „ne“.
Vlastnictví „doplňkového“ operátora (spolu-)
Pokud jde o jazyky
- vs.Ó-(vs.Ó-VS)=VS{\ displaystyle co {\ text {-}} (co {\ text {-}} C) = C}
![{\ displaystyle co {\ text {-}} (co {\ text {-}} C) = C}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7891a194ce1f526251d97f616c1920bf8fe4e1f5)
- VS⊆VS′⇒vs.Ó-VS⊆vs.Ó-VS′{\ displaystyle C \ subseteq C '\ Rightarrow co {\ text {-}} C \ subseteq co {\ text {-}} C'}
![{\ displaystyle C \ subseteq C '\ Rightarrow co {\ text {-}} C \ subseteq co {\ text {-}} C'}](https://wikimedia.org/api/rest_v1/media/math/render/svg/20bd542de64550ea83ae34b8f0123df639efcec1)
Na úrovni stroje
V případě deterministických tříd jsou třídy a jejich doplněk stejné: stačí převrátit dané odpovědi, což u nedeterministického stroje není, protože existence cesty přijímání není ekvivalentní skutečnosti, že všechny cesty přijímají.
Věty
Immerman-Szelepcsényiho věta
Ve své obecné formě uvádí Immerman-Szelepcsényiho věta rovnost:
NSPACE(s(ne))=co-NSPACE(s(ne)){\ displaystyle {\ text {NSPACE}} (s (n)) = {\ text {co-NSPACE}} (s (n))}![{\ text {NSPACE}} (s (n)) = {\ text {co-NSPACE}} (s (n))](https://wikimedia.org/api/rest_v1/media/math/render/svg/d559adbff2f929ca56e9616722fc09d240c285b8)
pro jakoukoli funkci .
s(ne)≥logne{\ displaystyle s (n) \ geq \ log n}![s (n) \ geq \ log n](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b5d4a7e4835ea1b4ec7d77eabdcca3aafb028d0)
Zejména NL = co-NL.
Otevřené problémy
Předpokládá se to , ale nikdy to nebylo prokázáno. Tato otázka souvisí s problémem P = NP následujícím způsobem: pokud P = NP, pak NP = co-NP, protože P = co-P.
vs.Ó-NEP≠NEP{\ displaystyle co {\ text {-}} NP \ neq NP}![{\ displaystyle co {\ text {-}} NP \ neq NP}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7d3944ab0baec01ff81019594f21782a207bca15)
Bibliografie
Poznámky a odkazy
-
Sylvain Perifel , Algoritmická složitost , Elipsy ,2014, 432 s. ( ISBN 9782729886929 , číst online ) , kap. 2.2 („neurčitý čas“) str.61.
-
(in) Sanjeev Arora a Boaz Barak , Výpočetní složitost: moderní přístup , Cambridge University Press , 2009( ISBN 0-521-42426-7 ) , kap. 2.6.1 („coNP“)
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">