Zadání
NSPACE(log3(n))
NTIME(2(n-1))
DTIME(2n)
DTIME(2n*log(n))
DSPACE(n)
Pokus o řešení
<big>1 ⊂ 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))