Zadání

  1. NSPACE(log3(n))

  2. NTIME(2(n-1))

  3. DTIME(2n)

  4. DTIME(2n*log(n))

  5. 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:

      1. Věta o vztazích c')

      2. <math>c_L^{\log^3 n} = 2^{\log^3 n \log c_L} \le 2^{log^4 n}</math>

      3. 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))