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

Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{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:

Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NSPACE}(f(n))\subseteq\cc{SPACE}(f^2(n))} Dobrze

Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NSPACE}(f(n))\subseteq\cc{SPACE}(\text{log}(n))} Źle

Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{SPACE}(f(n))\subseteq\cc{NSPACE}(f^2(n))} Źle

Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{SPACE}(f^2(n))\subseteq\cc{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 Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{L}} ma się do Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{PSPACE}} ?

Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{L}} zawiera się ściśle w Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{PSPACE}} Dobrze

nie wiadomo nic na ten temat Źle

Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{L}} zawiera się w Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{PSPACE}} , ale nie wiemy czy ściśle Źle

Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{PSPACE}} zawiera się ściśle w Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{L}} Źle

Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{PSPACE}} zawiera się w Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{L}} , ale nie wiemy czy ściśle Źle