Ein Problem ist PSPACE-vollständig, wenn es in PSPACE liegt und jedes PSPACE-Problem in polynomieller Zeit darauf reduzierbar ist.
Solche Probleme sind die schwersten Probleme in PSPACE unter dieser Reduktionsart.