Syntax highlighting of Archiv/TIN063 zkouska 2002-06-25

=Zadání=

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

=Pokus o řešení=

* <big>1 &sub; 2</big>
** <math>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})</math>
** Zatial asi nespravne
** Inkluze:
**# Věta o vztazích c')
**# <math>c_L^{\log^3 n} = 2^{\log^3 n \log c_L} \le 2^{log^4 n}</math>
**# 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))