Nella teoria della complessità computazionale, un problema decisionale è detto PSPACE-completo quando gli algoritmi che lo risolvono richiedono al minimo una quantità di memoria polinomiale rispetto alla dimensione dell'input e quando tutti i problemi risolti con memoria polinomiale possono essere ridotti ad esso in tempo polinomiale.
PSPACE-completo corrisponde alla classe di complessità computazionale che rappresenta i problemi decisionali che sono almeno altrettanto difficili dei problemi più difficili in PSPACE.