PSPACE
NP完全と同様に PSPACE に属する全ての問題から多項式時間変換可能であり、自らも PSPACE に属する問題を PSPACE完全 という。与えられた倉庫番ゲームが解を持つかの判定(一般倉庫番問題)や、n×n マスのリバーシや五目並べの与えられた局面から先手と後手のどちらに必勝法があるかの判定などが、PSPACE完全であることが知られている。