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: <wrongoption>w niedeterministycznym czasie liniowym</wrongoption> <wrongoption>w deterministycznej pamięci logarytmicznej</wrongoption> <rightoption>w niedeterministycznej pamięci logarytmicznej</rightoption> <wrongoption>w deterministycznym czasie liniowym</wrongoption> </quiz>

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: <rightoption>Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NSPACE(f(n))\subseteq\cc{SPACE}(f^2(n))} </rightoption> <wrongoption>Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NSPACE</quiz>(f(n))\subseteq\cc{SPACE}(\textnormal{log</quiz>(n))} </wrongoption> <wrongoption>Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{SPACE</quiz>(f(n))\subseteq\cc{NSPACE}(f^2(n))} </wrongoption> <wrongoption>Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{SPACE</quiz>(f^2(n))\subseteq\cc{NSPACE}(f(n))} </wrongoption> </quiz>

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

Zawieranie klas<quiz> 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}} ? {

Dobrze

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}}

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