IB102 úkol 12, příklad 2 Odevzdání: 19. 12. 2016
Jméno: UČO: Skupina:
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplňte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
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) L ≤p SAT =⇒ L ≤p TQBF
b) L ∈ NTIME 3n4 + 5 =⇒ L ∈ SPACE n12
c) L ∈ TIME n4 , R ∈ NTIME n2 =⇒ L · R ∈ NP
d) L ≤p ACC =⇒ L ∈ NP
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.