Zadání

  1. NSPACE(log<sup>3</sup>(n))

  2. NTIME(2<sup>(n-1)</sup>)

  3. DTIME(2<sup>n</sup>)

  4. DTIME(2<sup>n*log(n)</sup>)

  5. DSPACE(n)

Pokus o řešení

  • <big>1 ⊂ 2</big>

    • NS(log3n)⊆DT(cLlog3n)⊆DT(2log4n)⊂DT(2n−1)⊆NT(2n−1)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')

      2. cLlog⁡3n=2log⁡3nlog⁡cL≤2log4nc_L^{\log^3 n} = 2^{\log^3 n \log c_L} \le 2^{log^4 n}

      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^(nlog(n))

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

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