# Zadání #

1. NSPACE(log<sup>3</sup>(n))
1. NTIME(2<sup>(n-1)</sup>)
1. DTIME(2<sup>n</sup>)
1. DTIME(2<sup>n*log(n)</sup>)
1. DSPACE(n)

# Pokus o řešení #

* <big>1 ⊂ 2</big>
    * $NS(log^3 n) \subseteq DT(c_L^{log^3 n}) \subseteq DT(2^{log^4 n}) \subset DT(2^{n-1}) \subseteq NT(2^{n-1})$
    * Zatial asi nespravne
    * Inkluze:
        1. Věta o vztazích c')
        1. $c_L^{\log^3 n} = 2^{\log^3 n \log c_L} \le 2^{log^4 n}$
        1. NS <= /*c^log^3<2^log^4*/ DT < log(log^5)*log^5 << 2^n*/ DT <= NT

* 1 < 3 ... totéž

* 1 < 4 ... tím spíš

* 1 < 5 ... Savič + log^6<n

* 2 >= 3 ... fce si jsou rovné, 1/2 je jen konst

* 2 ? 4 ... těžko co říct

* 2 ? 5 ... není prostor na zabití konstanty c_L

* 3 < 4 ... log(2^n)*2^n << 2^(n*log(n))

* 3 ? 5 ... není prostor na zabití konstanty c_L

* 4 > 5 ... zabiji c_L pomocí fce log(log(n)) a pak 2^(n*log(log(n)))*log(2^(n*log(log(n)))) << 2^(n*log(n))