PSPACE

Nella teoria della complessità algoritmica, la classe di problemi PSPACE (da polynomial space) è l'insieme di tutti i problemi che possono essere risolti da una macchina di Turing deterministica usando una quantità di memoria di , dove è la dimensione dei dati di ingresso e è un qualsiasi valore finito. In altre parole, PSPACE include quei problemi che possono essere risolti da un algoritmo che utilizzi uno spazio di memoria la cui dimensione sia al più funzione polinomiale della dimensione dell'input.