IB102 – úkol 11, příklad 2 Odevzdání: 21. 12. 2015
Vypracoval(a): UČO:
Skupina:
2. [2 body] Nechť L a R jsou libovolné jazyky nad libovolnou abecedou Σ. O následujících
tvrzeních rozhodněte, zda jsou pravdivá, a svá rozhodnutí zdůvodněte:
a) NTIME(4n + 1010
) ⊆ SPACE(n2
)
b) L ≤p SAT =⇒ L ∈ NPSPACE
c) L /∈ NP =⇒ L ∈ coNP
d) L ∈ P, R ∈ NP =⇒ L ∪ R ∈ PSPACE