=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í=
1 < 2 ... 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))