die Komplexitätsklasse aller Probleme, die sich von Turing-Maschinen mit polynomiell vielen Zellen auf dem Arbeitsband berechnen lassen.

Bei Verwendung von nichtdeterministischen Turing-Maschinen mit polynomiellem Speicherplatz ergibt sich ebenfalls die Komplexitätsklasse PSPACE. Diese Komplexitätsklasse enthält alle Klassen der polynomiellen Hierarchie.