PSPACE

시간은 얼마가 걸리든 기억 공간을 입력 크기의 다항식만큼만 쓰면 풀 수 있는 결정 문제의 모임이다. 공간은 지우고 다시 쓸 수 있으므로 NP ⊆ PSPACE 이고, PSPACE ⊆ EXP 다. 「모든 x 에 대해, 어떤 y 가 있어, …」처럼 한정 기호가 번갈아 붙은 논리식의 참·거짓 판정(QBF)과 여러 2인 게임의 필승 판정이 PSPACE 에서 가장 어려운 문제다. P ≠ PSPACE 조차 증명되지 않았는데, 이는 P ≠ NP 보다 쉬워야 할 문제다.