對數空間（log space）

一台機器最少能用多麼少的記憶體，還能做出有趣的事？少得驚人：只要記住輸入中少數幾個位置就好。這就是對數空間的範疇。想像你在讀一本厚書，只用一個書籤加上寫在頁邊的小頁碼來記住進度：你從不抄寫整本書，只記得自己讀到哪。對數空間正是這種「只握有少數指標、而非資料本身」的紀律。

為什麼是 log n？要在 n 個輸入符號中指名一個位置，你需要一個介於 0 到 n 減 1 之間的索引，而把這個索引寫成二進位約需 log2(n) 個位元。所以 O(log n) 個工作格子恰好足夠儲存常數個這樣的指標與計數器，每一個都能遍歷整個輸入。因此對數空間機器無法儲存輸入（那需要 n 個格子），也無法儲存任何大型結構；它靠反覆重新掃描唯讀輸入帶、推進並比較指標來運作。正是唯讀輸入帶與工作帶的約定，才讓這個預算有意義。

對數空間是 L 類與 NL 類的家，也是我們例行研究的最小標準記憶體量。它之所以重要，是因為出乎意料地多自然任務都裝得進去（算術比較、簡單計數、以非確定方式檢查圖上的路徑），也因為對數空間歸約夠溫和，能比較問題而不偷渡額外能力。一個有用的健全性檢查：用 O(log n) 空間的機器最多只能跑多項式那麼多步，否則就必定重複某個格局而陷入迴圈，所以對數空間舒適地落在多項式時間之內。