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{c}\mathrm{o}\mathrm{N}\mathrm{L}$ 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{N}\mathrm{L}$ Źle

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

Klasa $\mathrm{D}\mathrm{P}$

zawiera w sobie $\mathrm{N}\mathrm{P}$ i $\mathrm{c}\mathrm{o}\mathrm{N}\mathrm{P}$ Dobrze

zawiera w sobie $\mathrm{P}\mathrm{H}$ Źle

zawiera się w $\mathrm{P}\mathrm{H}$ Dobrze

zawiera się w $\mathrm{N}\mathrm{P}$ i $\mathrm{c}\mathrm{o}\mathrm{N}\mathrm{P}$ Źle

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

$\mathrm{A}\mathrm{P}$ 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{N}\mathrm{P}$ Dobrze

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

maszyny z klasy $\mathrm{c}\mathrm{o}\mathrm{N}\mathrm{P}$ Ź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