空間複雜度類別（space-complexity class）
一旦我們同意衡量記憶體，就能依問題所需的記憶體多寡把它們分箱。空間複雜度類別就是這樣的一個箱子：它把所有「某台機器能在給定記憶體預算內判定」的語言收攏在一起。如果時間類別回答的是「在這麼多步內你能做什麼？」，空間類別回答的就是「用這麼多草稿紙你能做什麼？」。每一種預算的選擇都劃出一個不同的問題家族。
對一個函數 f(n)，確定型類別 SPACE(f(n)) 是所有「能被某台確定型圖靈機在長度 n 的輸入上用 O(f(n)) 個工作帶格子判定」的語言所成的集合。非確定型類別 NSPACE(f(n)) 相同，但機器可以猜測（一台非確定型圖靈機），並且只要至少有一條猜測序列導向接受就算接受，同樣在 O(f(n)) 個格子內。由這兩個定義建構出有名的地標：L 是 SPACE(log n)，NL 是 NSPACE(log n)，PSPACE 是所有常數 k 的 SPACE(n^k) 之聯集，依此沿著階梯往上。
用資源界限來定義類別是複雜度理論的骨幹：它讓我們能提出精確問題，如「L 是否嚴格地在 NL 之內？」或「PSPACE 是否等於 NPSPACE？」，並進而證明其中一些。兩個誠實的提醒。其一，界限是對最壞情況的 O(...) 上限，不是每個輸入上的確切記憶體。其二，我們通常要求 f 是空間可構造的（機器能標出 f(n) 個格子而不會超出），這是個溫和的技術條件，階層定理倚賴它；日常函數 log n、n、n^2、2^n 全都滿足。
SPACE(n^2) 包含所有能用至多平方數量的工作格子判定的語言。整個 PSPACE 類別是所有多項式上的聯集 SPACE(n) ∪ SPACE(n^2) ∪ SPACE(n^3) ∪ ...；用哪個多項式無關緊要，重點只在於存在某個多項式界限成立。
一個空間類別是所有能在給定記憶體預算 f(n) 內判定的語言所成的集合。
階層定理需要 f 是空間可構造的。這是個溫和的條件，所有常見界限（log n、n、n^2、2^n）都滿足，實務上並非真正的限制。