Immerman-Szelepcsenyi 定理（Immerman-Szelepcsenyi theorem）

這是讓空間行為異於時間的第二個大驚喜。非確定型機器擅長靠猜測來確認某物存在（一條路徑、一個滿足指派），卻似乎對確認某物「不存在」束手無策，因為沒有單一個物件可猜。對時間，我們完全不知道 NP 是否等於 co-NP（多數人相信不等於）。然而對非確定型空間，看似不可能的事成為可能：它對補集封閉。Immerman-Szelepcsenyi 定理（Neil Immerman 與 Robert Szelepcsenyi 各自獨立，1987）證明了它。

形式上，對任何至少為 log n 的空間界限 f(n)，NSPACE(f(n)) 等於 co-NSPACE(f(n))。頭條情形是 NL 等於 co-NL：一個能在非確定型對數空間解的問題，其補集也能在非確定型對數空間解。以有向可達性為例。確認 t「可」由 s 到達，對 NL 機器很容易（猜出那條路徑）。巧妙之處在於只用對數空間確認 t「不可」到達。證明用了歸納計數：機器以非確定方式算出由 s 在 k 步內可達的頂點「確切數目」，並從 k 建到 k+1；一旦知道這個計數，它就能逐個頂點地驗證 t 不在可達集合中，全程只儲存少數幾個計數器。

這真正令人震驚，因為時間的類比陳述（NP 等於 co-NP）被廣泛相信為假、且完全未解。空間又能辦到的原因仍歸結於重用：計數與重新驗證可以覆寫同樣的格子，而 NP 驗證器無法在其時間預算內重新推導出「見證不存在」。這個定理也整理了上下文相關語言（NSPACE(n)）的版圖，解決了一個關於它們對補集封閉性的長期問題。提醒：這個計數技巧需要可達集合的確切大小，而那是機器自己猜出再以非確定方式驗證的；它很微妙，不是一行就能講完的論證。