PSPACE
PSPACE は、交替性チューリング機械で多項式時間で解ける問題の集合としても定式化できる。この場合、APTIME あるいは単に AP とも呼ぶ。
PSPACE は、IP と呼ばれる対話型証明系で認識できる全言語にも対応する。