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{N}\mathrm{L}$ 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{N}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(f(n))\subseteq \mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(f^2(n))$ Dobrze

$\mathrm{N}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(f(n))\subseteq \mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(\text{log}(n))$ Źle

$\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(f(n))\subseteq \mathrm{N}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(f^2(n))$ Źle

$\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(f^2(n))\subseteq \mathrm{N}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}(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{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$?

$\mathrm{L}$ zawiera się ściśle w $\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$ Dobrze

nie wiadomo nic na ten temat Źle

$\mathrm{L}$ zawiera się w $\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$, ale nie wiemy czy ściśle Źle

$\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$ zawiera się ściśle w $\mathrm{L}$ Źle

$\mathrm{P}\mathrm{S}\mathrm{P}\mathrm{A}\mathrm{C}\mathrm{E}$ zawiera się w $\mathrm{L}$, ale nie wiemy czy ściśle Źle