Zkouška ze Složitost II (TIN063)

  • Stejná písemka byla i 05.06.2009

  • Je potvrzene ze takhle je zcela spravne :)

Zadání

  1. NTIME(n)

  2. NSPACE(log<sup>2</sup>(n))

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

  4. DTIME(2<sup>n^2</sup>)

  5. DSPACE(n*log(n))

Pokus o řešení

1 ? 2

1 ⊂ 3 ... NT->DT: 2<sup>nlog(log(n))</sup>, DT vs. DT: 2<sup>nlog(n)</sup> ∈ ω(2<sup>n*log(log(n))</sup>nlog(log(n))*log(2))

1 ⊂ 4 ... jako 1 ⊂ 3

1 ⊂ 5 ... NT(n) ⊆ DS(n) ⊂ DS(n*log(n)) - rozsirena veta o vztazich b') (ta co je spatne ve Strojilovi a rika ze jen NT ⊆ NS) a prostorova hiearchie

2 ⊂ 3 ... NS->DT: 2<sup>log^2(n)*log(log(n))</sup>, jako 1 ⊂ 3

2 ⊂ 4 ... jako 1 ⊂ 3

2 ⊂ 5 ... Savič: NS->DS: log<sup>4</sup>(n), DS vs. DS: n*log(n) ∈ ω(log<sup>4</sup>(n))

3 ⊂ 4 ... DT vs. DT: 2<sup>n^2</sup> ∈ ω(n*log(n)2<sup>nlog(n)</sup>*log(2))

3 ? 5

5 ⊂ 4 ... jako 1 ⊂ 3