Zadání

1. DSPACE(n² log(n))

2. DTIME(2^{n log(n)})

3. NSPACE(n)

4. NSPACE(n log(n))

5. NTIME(2^{n log(n) - 2})

Pokus o řešení

• 1 ? 2

• 2 > 3

TODO jak se to ukáže ?

• 3 <= 4

  • n <= n log(n)

• 4 ? 5

• 5 ? 1

• 1 > 3

  • NSPACE(n) ⊆ DSPACE(n²) ⊂ DSPACE(n² log(n))

  • 1. • savič, 2. - věta o det. prost. hierarchii

• 2 ? 4

• 3 < 5

  • pozorování: NTIME(2^{n log(n) - 2}) = NTIME(1/2 * 2^{n log(n)}) = NTIME(2^{n log(n)})

  • víme z 2 > 3: NSPACE(n) ⊂ DTIME(2^{n log(n)})

  • triviálně: DTIME(2^{n log(n)}) ⊆ NTIME(2^{n log(n)})

• 4 ? 1

• 5 >= 2

  • pozorování: NTIME(2^{n log(n) - 2}) = NTIME(1/2 * 2^{n log(n)}) = NTIME(2^{n log(n)})

  • triviálně: DTIME(2^{n log(n)}) ⊆ NTIME(2^{n log(n)})