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

From Studia Informatyczne

Liniowe przyspieszanie działania maszyny uzyskujemy poprzez:

zwiększenie liczby stanów

zmniejszenie alfabetu maszyny

zwiększenie alfabetu maszyny

wstępne przetworzenie danych

zmniejszenie liczby stanów


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

w niedeterministycznym czasie liniowym

w deterministycznej pamięci logarytmicznej

w niedeterministycznej pamięci logarytmicznej

w deterministycznym czasie liniowym


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

c^{f(n)}

f(n)^c

f(n)

cf(n)


Tezą twierdzenia Savitcha jest:

\cc{NSPACE}(f(n))\subseteq\cc{SPACE}(f^2(n))

\cc{NSPACE}(f(n))\subseteq\cc{SPACE}(\textnormal{log}(n))

\cc{SPACE}(f(n))\subseteq\cc{NSPACE}(f^2(n))

\cc{SPACE}(f^2(n))\subseteq\cc{NSPACE}(f(n))


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

klasy deterministyczne

klasy niedeterministyczne czasowe

klasy niedeterministyczne pamięciowe


Która rodzina klas podlega hierarchii?

tylko złożoności czasowej

tylko złożoności pamięciowej

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

żadne z powyższych


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

\cc{L} zawiera się ściśle w \cc{PSPACE}

nie wiadomo nic na ten temat

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

\cc{PSPACE} zawiera się ściśle w \cc{L}

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