對數空間歸約（log-space reduction）

歸約是把一個問題翻譯成另一個問題的翻譯員，使得對後者的答案能直接給出前者的答案。但翻譯員本身會用掉一些資源，而要比較記憶體極低的類別，我們需要一個本身就省記憶體的翻譯員。對數空間歸約是只用 O(log n) 工作記憶體就能計算的翻譯。它是你研究 L 與 NL 時所用的溫和手術刀，精細到不會壓過你正在解剖的那些類別。

形式上，從語言 A 到 B 的對數空間歸約，是一個函數 f，能被一台用 O(log n) 工作帶空間的確定型圖靈機計算，使得 w 屬於 A 若且唯若 f(w) 屬於 B。一個微妙之處：輸出 f(w) 本身可能很長（長達多項式長度），比對數空間的工作帶還長，所以機器把它寫到一條無法讀回的獨立唯寫輸出帶上，由左到右產生答案，而過程中始終只記住少數幾個指標。這正是定義 NL 完全與 L 困難的那種溫和歸約。

為何堅持用對數空間，而非更熟悉的多項式時間歸約？因為要分離像 L 與 NL 這麼小的類別，歸約必須比類別本身更弱。多項式時間歸約能做的遠多於對數空間機器，用它會讓翻譯偷渡能力、使連瑣碎問題看起來都像完全，我們在意的區別就會崩塌。兩個事實讓理論保持乾淨：對數空間歸約可複合（串接兩個仍待在對數空間，這並不顯然，需要一個巧妙的論證），而且 L 與 NL 對它都封閉，所以完全性表現良好。