複雜度類別地圖（complexity-class map）
從個別定義退後一步，一片地景便映入眼簾：一條層層嵌套的類別之鏈，每一個都包含於下一個，描繪出時間與記憶體預算如何相互關聯。最主要的鏈，由資源最少到最多，是 L 包含於 NL 包含於 P 包含於 NP 包含於 PSPACE 包含於 EXPTIME。讀它就像讀一系列一個畫在另一個裡面、愈來愈大的圓圈，每一圈都是比它內部更慷慨的資源預算。這一張圖組織了本領域幾乎所有的東西。
每個包含都有一句話的理由。L 包含於 NL，因為確定性是非確定性的特例。NL 包含於 P，因為對數空間機器只有多項式數量的格局，而它們之間的可達性可在多項式時間內解出。P 包含於 NP，因為驗證器可以忽略其證書、直接重新計算。NP 包含於 PSPACE，因為你可以一次一個地試遍每個候選證書、重用同樣的記憶體。PSPACE 包含於 EXPTIME，因為多項式空間只容許 2^(多項式) 個格局，所以不迴圈的機器會在指數時間內停機。圍繞 NP 層疊著 co-NP 與多項式階層（Sigma 與 Pi 層級），全都在 PSPACE 之內；平行的空間類別則延伸這幅圖（PSPACE 在 EXPSPACE 之內，依此類推）。
現在來殘酷的誠實，而這正是這張地圖的全部重點。我們知道兩個「端點」不同：由階層定理，L 嚴格在 PSPACE 之內、P 嚴格在 EXPTIME 之內，所以這條鏈確實在某處真的變大。我們知道 NL = co-NL（Immerman-Szelepcsenyi）與 PSPACE = NPSPACE（Savitch），是兩個令人愉快的塌縮。但中間幾乎每個個別包含都是「被猜測」、而非已證明的：L 是否等於 NL、L 是否等於 P、P 是否等於 NP、NP 是否等於 PSPACE，全都是著名的未解問題。完全有可能（雖然被強烈不信）從 L 一路到 PSPACE 其實偷偷是同一個類別。這張地圖既顯示了什麼必定為真、也顯示了我們希望為真的；分辨「已證明」與「僅是相信」，是本學科最深的未竟之業。
你可以倚靠的已知嚴格事實：由空間階層定理 L 嚴格在 PSPACE 之內，由時間階層定理 P 嚴格在 EXPTIME 之內。所以在 L 在 NL 在 P 在 NP 在 PSPACE 這條鏈上的某處，至少有一個包含必定是嚴格的，同樣地在 P 在 NP 在 PSPACE 在 EXPTIME 之內亦然，但我們還無法指出是「哪一個」。
L 在 NL 在 P 在 NP 在 PSPACE 在 EXPTIME：兩端可證明不同，但中間幾乎每個包含都未解。
鏈中大多數包含（L 對 NL、L 對 P、P 對 NP、NP 對 PSPACE）都是「被猜測」、而非已證明的。真正已知的只有端點分離（階層定理：L 嚴格在 PSPACE 之內、P 嚴格在 EXPTIME 之內）以及塌縮 NL = co-NL、PSPACE = NPSPACE。