PSPACE-완전
다항식 공간 내에서 해결 가능한 문제들 중 가장 어려운 문제 부류를 의미한다. 시간 복잡도와 상관없이 메모리 사용량이 제한된 환경에서 해결해야 하며 많은 최적 제어 및 게임 이론 문제들이 이 범주에 속해 계산적으로 매우 까다롭다.