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 $\mathrm {coNL}$ Dobrze

UNDIRECTED REACHABILITY należy do klasy $\mathrm {L}$ Źle

REACHABILITY należy do klasy $\mathrm {L}$ Źle

UNDIRECTED REACHABILITY należy do klasy $\mathrm {NL}$ Źle

REACHABILITY należy do klasy $\mathrm {NL}$ Źle

Klasa $\mathrm {DP}$

zawiera w sobie $\mathrm {NP}$ i $\mathrm {coNP}$ Dobrze

zawiera w sobie $\mathrm {PH}$ Źle

zawiera się w $\mathrm {PH}$ Dobrze

zawiera się w $\mathrm {NP}$ i $\mathrm {coNP}$ Źle

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

$\mathrm {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 $\sum _{i}\mathrm {P}$ jest definiowana poprzez wyrocznię na niższy poziom oraz:

maszyny z klasy $\mathrm {NP}$ Dobrze

maszyny z klasy $\mathrm {P}$ Źle

maszyny z klasy $\mathrm {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