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
niedeterministycznej pamięciowej są zamknięte na dopełnienie
deterministycznej czasowej są zamknięte na dopełnienie
niedeterministycznej czasowej są zamknięte na dopełnienie
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}}
UNDIRECTED REACHABILITY należy do klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{L}}
REACHABILITY należy do klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{L}}
UNDIRECTED REACHABILITY należy do klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NL}}
REACHABILITY należy do klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NL}}
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}}
zawiera w sobie Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{PH}}
zawiera się w Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{PH}}
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}}
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
w alternującej pamięci wielomianowej
w niedeterministycznej pamięci wielomianowej
w deterministycznej pamięci wielomianowej
w alternującym czasie wielomianowym
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}}
maszyny z klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{P}}
maszyny z klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{coNP}}
Czy hierarchia wielomianowa ma problemy zupełne?
na każdym poziomie, lecz nie jako całość
jako całość, natomiast na poziomach nie
nie posiada zarówno jako całość jak i na poziomach
na każdym poziomie i jako całość
