IB102 – úkol 11, příklad 2 Odevzdání: 15. 12. 2014
Vypracoval(a): UČO:
Skupina:
2. [2 body] Nechť L je libovolný jazyk nad libovolnou abecedou Σ. O následujících
tvrzeních rozhodněte, zda jsou pravdivá, a svá rozhodnutí zdůvodněte:
a) L ≤p TQBF =⇒ L ∈ PSPACE
b) NTIME(5n3
) ⊆ SPACE(n8
)
c) coNP ⊆ PSPACE
d) L ∈ SPACE(2n
) =⇒ L /∈ P
Bonus [1 bod] Dále rozhodněte platnost následujícího tvrzení a své rozhodnutí zdů-
vodněte:
L ≤p TQBF =⇒ L je PSPACE-úplný