Zkouška ze [Složitost II](Složitost%20II) (TIN063)

* Stejná písemka byla i 05.06.2009
* Je potvrzene ze takhle je zcela spravne :)

# Zadání #

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

# Pokus o řešení #

1 ? 2

1 ⊂ 3 ... NT->DT: 2<sup>n*log(log(n))</sup>, DT vs. DT: 2<sup>n*log(n)</sup> ∈ ω(2<sup>n*log(log(n))</sup>*n*log(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>n*log(n)</sup>*log(2))

3 ? 5

5 ⊂ 4 ... jako 1 ⊂ 3