PSPACE（多項式空間）
PSPACE 是「用多項式量的草稿記憶體就能解、無論計算花多久」的問題類別。想像一個西洋棋引擎在分析一個局面：它可能探索多到驚人的走法序列，遠超過它能列出的記憶量，但它可以一次次重用同一個棋盤，探索完每一步後就把它復原。只要有一個多項式大小的棋盤、加上一疊多項式深度的待記走法，原則上它就能判定誰會贏。這種「記憶體有界但時間無界」的範疇就是 PSPACE。
形式上，PSPACE 是所有常數 k 的 SPACE(n^k) 之聯集：能被一台用至多多項式數量工作格子的確定型圖靈機判定的語言。由 Savitch 定理，允許非確定性並不會擴大它，所以 PSPACE 等於 NPSPACE，我們直接說 PSPACE。它位於何處？P 中的每個問題都在 PSPACE（多項式時間機器至多碰多項式數量的格子），NP 中的每個問題也是，於是 P 包含於 NP 包含於 PSPACE。理解 PSPACE 為何如此龐大的關鍵直覺是重用：一台 PSPACE 機器可能跑指數時間、循環經過多達 2^(多項式) 個格局，卻始終不需要超過多項式的記憶體。
PSPACE 是雙人賽局與「交錯量詞推理」（TQBF 問題）的天然家。它最難的問題——PSPACE 完全的那些——捕捉像「第一位玩家是否有必勝策略？」這樣的問題，這需要你考慮「存在一步走法，使得對所有回應，都存在一步走法 ...」這種一來一往，恰好填滿多項式空間。誠實的提醒：雖然 P 包含於 PSPACE，但這個包含是否嚴格（即 P 是否不等於 PSPACE）仍未解，NP 對 PSPACE 也是。我們確實知道由空間階層定理 PSPACE 嚴格在 EXPSPACE 之內，且包含於 EXPTIME，但要確切釘住它在 P、NP、EXPTIME 之間的位置仍超出我們能力。
判定一個帶量詞、完全加括號的布林公式（如「對所有 x，存在 y，(x 或 y) 且 (非 x 或 非 y)」）是否為真屬於 PSPACE：遞迴地試最外層變數的兩個值，每個分支重用同一塊工作區，並在試下一個前把它復原。遞迴深度是變數個數（多項式），所以即使它探索了指數多的指派，多項式空間仍足夠。
PSPACE = 多項式記憶體、可能指數時間；重用同樣的格子正是它如此強大的原因。
P 包含於 NP 包含於 PSPACE，但這些包含是否有任何一個嚴格仍未解。我們只知道 PSPACE 嚴格在 EXPSPACE 之內（空間階層）且包含於 EXPTIME。