一个判定问题是多项式空间PSPACE完全（PSPACE-complete）的当且仅当它满足如下两个条件：①该问题属于多项式空间PSPACE类。②所有PSPACE类里的问题都能在多项式时间里归约到该问题。

PSPACE完全的问题可以视为PSPACE类内最难的问题。因此PSPACE=P当且仅当一个PSPACE完全的问题能在多项式时间内判定。类似地PSPACE=NP当且仅当一个PSPACE完全的问题属于NP类。

有很多计算问题是PSPACE完全的，以下是其中最著名的几大类。①推广后的棋类博弈游戏（generalized game）（这里的推广是指博弈的棋盘可以任意大）。亚马逊棋 （amazons）、六贯棋 （hex）、麻将接龙、超级马里奥兄弟游戏 （super Mario Bros）、多项式长度的围棋（即双方棋手在多项式步后停止）、黑白卵石博弈 （black-white pebble game）等。②逻辑问题。量词命题逻辑的可满足性问题（quantified Boolean satisfiability）、一阶逻辑模型检测问题（first-order logic model-checking）、带等词的一阶逻辑判定问题（first-order theory of equality）、二进制串在字典序下的一阶逻辑问题 （first-order theory of binary strings under lexicographic ordering）等。③自动机和形式语言。非确定有限自动机相等判定（equivalence problem for nondeterministic finite automata）、非确定有限自动机最小化（minimizing nondeterministic finite automata）、正则表达式的相等判定（equivalence problems for regular expressions）、线性语法的覆盖问题 (covering of linear grammars)等。④图论。当图以某些方式压缩表示（succinct representations）时，如以布尔电路和有序二元判定图（ordered binary decision diagrams）的方式，很多原来属于的问题都成为完全的。例如连通性问题、平面图判定问题（planarity）、无环问题（acyclicity）、欧拉回路问题（Eulerian path）等。