# Zadání #

1. DSPACE(n<sup>2</sup> log(n))
1. DTIME(2<sup>n log(n)</sup>)
1. NSPACE(n)
1. NSPACE(n log(n))
1. NTIME(2<sup>n log(n) - 2</sup>)

# Pokus o řešení #

* 1 ? 2

* 2 > 3

[TODO jak se to ukáže ?](TODO%20jak%20se%20to%20ukáže%20%3F)

* 3 <= 4
    * n <= n log(n)

* 4 ? 5

* 5 ? 1

* 1 > 3
    * NSPACE(n) ⊆ DSPACE(n<sup>2</sup>) ⊂ DSPACE(n<sup>2</sup> log(n))
    * 1. - savič, 2. - věta o det. prost. hierarchii

* 2 ? 4

* 3 < 5
    * pozorování: NTIME(2<sup>n log(n) - 2</sup>) = NTIME(1/2 * 2<sup>n log(n)</sup>) = NTIME(2<sup>n log(n)</sup>)
    * víme z 2 > 3: NSPACE(n) ⊂ DTIME(2<sup>n log(n)</sup>)
    * triviálně: DTIME(2<sup>n log(n)</sup>) ⊆ NTIME(2<sup>n log(n)</sup>)

* 4 ? 1

* 5 >= 2
    * pozorování: NTIME(2<sup>n log(n) - 2</sup>) = NTIME(1/2 * 2<sup>n log(n)</sup>) = NTIME(2<sup>n log(n)</sup>)
    * triviálně: DTIME(2<sup>n log(n)</sup>) ⊆ NTIME(2<sup>n log(n)</sup>)