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: <wrongoption>w niedeterministycznym czasie wielomianowym</wrongoption> <wrongoption>w alternującej pamięci wielomianowej</wrongoption> <wrongoption>w niedeterministycznej pamięci wielomianowej</wrongoption> <wrongoption>w deterministycznej pamięci wielomianowej</wrongoption> <rightoption>w alternującym czasie wielomianowym</rightoption> </quiz>
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ść
