PSPACE-completo

Questa voce o sezione sull'argomento informatica non è ancora formattata secondo gli standard.

Commento: mancano i template di citazione, con una nota inserita semplicemente come url, e le formule matematiche (al momento la notazione è inserita con il corsivo)

---

Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento.

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.