Złożoność obliczeniowa/Test 3: Klasy złożoności obliczeniowej

Liniowe przyspieszanie działania maszyny uzyskujemy poprzez:

zwiększenie liczby stanów Dobrze

zmniejszenie alfabetu maszyny Źle

zwiększenie alfabetu maszyny Dobrze

wstępne przetworzenie danych Dobrze

zmniejszenie liczby stanów Źle

$\mathrm {NL}$ jest klasą języków, które mogą być akceptowane:

w niedeterministycznym czasie liniowym Źle

w deterministycznej pamięci logarytmicznej Źle

w niedeterministycznej pamięci logarytmicznej Dobrze

w deterministycznym czasie liniowym Źle

W jak wielu konfiguracjach może znaleźć się maszyna Turinga o złożoności pamięciowej $f(n)$ (asymptotycznie)?

$c^{f(n)}$ Dobrze

$f(n)^{c}$ Źle

$f(n)$ Źle

$cf(n)$ Źle

Tezą twierdzenia Savitcha jest:

$\mathrm {NSPACE} (f(n))\subseteq \mathrm {SPACE} (f^{2}(n))$ Dobrze

$\mathrm {NSPACE} (f(n))\subseteq \mathrm {SPACE} ({\text{log}}(n))$ Źle

$\mathrm {SPACE} (f(n))\subseteq \mathrm {NSPACE} (f^{2}(n))$ Źle

$\mathrm {SPACE} (f^{2}(n))\subseteq \mathrm {NSPACE} (f(n))$ Źle

Klasy zamknięte na operację dopełnienia to:

klasy deterministyczne Dobrze

klasy niedeterministyczne czasowe Źle

klasy niedeterministyczne pamięciowe Dobrze

Która rodzina klas podlega hierarchii?

tylko złożoności czasowej Źle

tylko złożoności pamięciowej Źle

zarówno złożoności czasowej jak i pamięciowej Dobrze

żadne z powyższych Źle

Jak klasa $\mathrm {L}$ ma się do $\mathrm {PSPACE}$?

$\mathrm {L}$ zawiera się ściśle w $\mathrm {PSPACE}$ Dobrze

nie wiadomo nic na ten temat Źle

$\mathrm {L}$ zawiera się w $\mathrm {PSPACE}$, ale nie wiemy czy ściśle Źle

$\mathrm {PSPACE}$ zawiera się ściśle w $\mathrm {L}$ Źle

$\mathrm {PSPACE}$ zawiera się w $\mathrm {L}$, ale nie wiemy czy ściśle Źle