PSPACE enthält Entscheidungsprobleme, die mit polynomiell viel Speicher gelöst werden können.
Die Laufzeit darf dabei exponentiell sein.