PSPACE Flashcards
1
Q
Opakovanie, aký je vzťah NP a PSPACE?
A
NP⊆PSPACE
2
Q
Definuj PSPACE-úplnosť
A
Jazyk L0 je PSPACE-úplný, ak L0 je v PSPACE a každý jazyk L z PSPACE je polynomiálne transformovateľný na L0
3
Q
Definuj úplne kvantifikované formuly, aj s príkladom
A
Definícia 8.2 na 79
4
Q
Definuj TQBF
A
str. 79
5
Q
Dokáž, že TQBF je PSPACE-úplný
A
str. 80
6
Q
Aké sú príklady PSPACE-úplných problémov?
A
Hra BF, hra GG
7
Q
Definuj hru BF, a že je PSPACE-úplná
A
str. 83
8
Q
Definuj hru GG a že je PSPACE-úplná
A
str. 84
