Złożoność obliczeniowa/Test 13: Pamięć logarytmiczna i hierarchia wielomianowa

Twierdzenie Immermana-Szelepcsényi'ego mówi o tym, że klasy złożoności:

deterministycznej pamięciowej są zamknięte na dopełnienie Źle

niedeterministycznej pamięciowej są zamknięte na dopełnienie Dobrze

deterministycznej czasowej są zamknięte na dopełnienie Źle

niedeterministycznej czasowej są zamknięte na dopełnienie Źle

W dowodzie twierdzenia Immermana-Szelepcsényi'ego korzystamy z faktu, iż:

REACHABILITY należy do klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{coNL}} Dobrze

UNDIRECTED REACHABILITY należy do klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{L}} Źle

REACHABILITY należy do klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{L}} Źle

UNDIRECTED REACHABILITY należy do klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NL}} Źle

REACHABILITY należy do klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NL}} Źle

Klasa Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{DP}}

zawiera w sobie Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NP}} i Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{coNP}} Dobrze

zawiera w sobie Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{PH}} Źle

zawiera się w Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{PH}} Dobrze

zawiera się w Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NP}} i Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{coNP}} Źle

Maszyny alternujące są specjalnym przypadkiem maszyn niedeterministycznych. {FALSE}

Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{AP}} jest klasą języków, które mogą być akceptowane:

w niedeterministycznym czasie wielomianowym Źle

w alternującej pamięci wielomianowej Źle

w niedeterministycznej pamięci wielomianowej Źle

w deterministycznej pamięci wielomianowej Źle

w alternującym czasie wielomianowym Dobrze

Klasa Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \sum_{i} \cc{P}} jest definiowana poprzez wyrocznię na niższy poziom oraz:

maszyny z klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NP}} Dobrze

maszyny z klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{P}} Źle

maszyny z klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{coNP}} Źle

Czy hierarchia wielomianowa ma problemy zupełne?

na każdym poziomie, lecz nie jako całość Dobrze

jako całość, natomiast na poziomach nie Źle

nie posiada zarówno jako całość jak i na poziomach Źle

na każdym poziomie i jako całość Źle