Savitch 定理（Savitch's theorem）
/ SAV-itch /
這是複雜度理論中真正的驚喜之一。對時間而言，我們強烈懷疑讓機器猜測（非確定性）會帶來巨大、可能呈指數的提升：那就是 P 對 NP 之謎。但對空間而言，猜測竟然只幫一點點忙。Savitch 定理（Walter Savitch，1970）證明非確定型空間至多只比確定型空間強大平方倍，以複雜度的標準來看是極小的差距。把空間界限的指數加倍，就是移除全部猜測的整個代價。
精確地說，對任何至少為 log n 的合理函數 f(n)，NSPACE(f(n)) 包含於 SPACE(f(n)^2)。證明是對可達性問題一個漂亮的分治。要檢查格局 A 能否在至多 2^k 步內到達格局 B，就問：是否存在一個中點 M，使得 A 在至多 2^(k-1) 步內到達 M，且 M 在至多 2^(k-1) 步內到達 B？對每一半遞迴，並依序嘗試每個可能的中點 M。這個遞迴只有 k = O(f(n)) 層深，而每層儲存一個格局（佔 O(f(n)) 空間），所以總工作空間是 O(f(n)) 乘以 O(f(n)) = O(f(n)^2)。這個取捨很鮮明：這個確定型模擬出色地重用空間，卻花指數時間。
頭條結果是 PSPACE = NPSPACE：因為多項式的平方仍是多項式，確定型與非確定型多項式空間重合，所以我們從不費心寫 NPSPACE。同理 NL 包含於 SPACE((log n)^2)。這恰與時間世界相反，那裡我們無法把 NP 塌縮進 P。空間能辦到這點的原因是重用：遞迴在每層覆寫同樣的格子，而非需要新鮮記憶體，這是時間預算無法模仿的。提醒：抹除非確定性的代價付在時間上，而非空間；那台確定型機器可能跑得呈指數久。
套用到 NL：有向可達性屬於 NL，而 Savitch 的遞迴以 O((log n)^2) 空間確定地解出它。要問「s 是否在 <= n 步內到達 t？」，就嘗試每個中點頂點 m，並遞迴地問「s 在 <= n/2 步內到達 m」與「m 在 <= n/2 步內到達 t」。遞迴約 log n 層深，每層儲存一個 O(log n) 位元的頂點，總計 O((log n)^2)。
Savitch 的中點遞迴以平方空間移除非確定性，代價是指數時間。
平方的空間代價是用時間償還的：確定型模擬可能比非確定型原版跑得呈指數久。Savitch 是用時間換空間，而非相反。