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}
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 \}}
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}
- VS⊆VS′⇒vs.Ó-VS⊆vs.Ó-VS′{\ displaystyle C \ subseteq C '\ Rightarrow co {\ text {-}} C \ subseteq co {\ text {-}} C'}
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))}pro jakoukoli funkci .
s(ne)≥logne{\ displaystyle s (n) \ geq \ log n}
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}
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;">