Uzupełniające (złożoność)
W teorii złożoności (dziedzina informatyki teoretycznej ) mówimy o dopełnieniu klasy C, oznaczonej co-C lub coC, aby oznaczyć zbiór języków komplementarnych do języków klasy. Ten operator prowadzi do rozważenia nowych klas jako co-NP , dopełnienia NP .
Definicja formalna
Uzupełnienie języka
Rozważ język na alfabecie i zestaw słów na . Zatem uzupełnienie , zaznaczone tutaj, jest . W szczególności zauważamy, że dopełnienie jest .
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)
Uzupełnienie zajęć językowych
Niech C oznacza klasę, to jego komplementarne CO-C: .
vso-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)
Jeśli chodzi o maszyny Turinga
Jeśli weźmiemy punkt widzenia maszyn i problemów Turinga , to komplementarnym problemem decyzyjnym jest taki, w którym odwróciliśmy „tak” i „nie”, aby odpowiedzieć na pytanie.
Własność operatora „komplementarnego” (co-)
Pod względem języków
- vso-(vso-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′⇒vso-VS⊆vso-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 poziomie maszyny
W przypadku klas deterministycznych klasy i ich dopełnienie są równe: wystarczy odwrócić dane odpowiedzi, co nie ma miejsca w przypadku maszyny niedeterministycznej, gdyż istnienie ścieżki akceptującej nie jest równoznaczne z faktem, że wszystko ścieżki się akceptują.
Twierdzenia
Twierdzenie Immermana-Szelepcsényiego
W swojej ogólnej formie twierdzenie Immermana-Szelepcsényiego stwierdza równość:
NSPACE(s(nie))=co-NSPACE(s(nie)){\ Displaystyle {\ tekst {NSPACE}} (s (n)) = {\ tekst {co-NSPACJA}} (s (n))}![{\ text {NSPACJA}} (s (n)) = {\ text {co-NSPACJA}} (s (n))](https://wikimedia.org/api/rest_v1/media/math/render/svg/d559adbff2f929ca56e9616722fc09d240c285b8)
do dowolnej funkcji .
s(nie)≥lognie{\ Displaystyle s (n) \ geq \ log n}![s (n) \ geq \ log n](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b5d4a7e4835ea1b4ec7d77eabdcca3aafb028d0)
W szczególności NL = co-NL.
Otwarte kwestie
Przypuszcza się , że nigdy tego nie pokazano. To pytanie jest powiązane z problemem P = NP w następujący sposób: jeśli P = NP, to NP = co-NP, ponieważ P = co-P.
vso-NIEP.≠NIEP.{\ displaystyle co {\ text {-}} NP \ neq NP}![{\ displaystyle co {\ text {-}} NP \ neq NP}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7d3944ab0baec01ff81019594f21782a207bca15)
Bibliografia
Uwagi i odniesienia
-
Sylvain Perifel , Złożoność algorytmiczna , Elipsy ,2014, 432 s. ( ISBN 9782729886929 , czytaj online ) , rozdz. 2.2 („Niedeterministyczny czas”) s. 61.
-
(w) Sanjeev Arora i Boaz Barak , Złożoność obliczeniowa: nowoczesne podejście , Cambridge University Press , 2009( ISBN 0-521-42426-7 ) , rozdz. 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;">