PSPACE ist die Klasse aller Sprachen, die Spiele mit 2 Spielern kodieren.

Jede PSPACE-vollständige Sprache ist coNP-schwer.

Jede NP-schwere Sprache ist PSPACE-vollständig.

TQBF ist PSPACE-schwer, aber nicht in PSPACE.

Jede PSPACE-vollständige Sprache ist NP-schwer.

PSPACE ist die Klasse aller Sprachen, die von deterministischen Turing-Maschinen mit polynomiellen Platzbedarf entschieden werden können.