L 類（class L）

L 是「幾乎什麼都不必記就能解」的問題俱樂部：不管輸入多大，都只記固定的少數指標與計數器。想像一位稽核員必須查核一本巨大的帳冊，卻只獲准用幾張便利貼。他無法影印整本帳冊，只能來回翻閱，在這裡記個位置、那裡記個累計。這位記憶力受限的稽核員仍能完成的任務，正好就是 L 裡的問題。

形式上，L 等於 SPACE(log n)：所有能被一台確定型圖靈機在長度 n 的輸入上用 O(log n) 個工作帶格子判定的語言，其中輸入本身躺在一條獨立的唯讀帶上。L 代表 logarithmic（對數）。由於 O(log n) 個位元只能編碼常數個指向輸入的索引，L 機器靠一遍又一遍重新掃描唯讀帶來處理資料，從不建立自己的大型記憶。許多家常操作都住在這裡：判定整除性、比較或相加數字、檢查括號是否配對、辨識簡單模式。

L 之所以重要，是作為我們能清楚立足的最底層階梯，也是 NL 的確定型對應物。我們知道 L 包含於 NL 包含於 P，所以 L 裡的任何東西在時間上也是易處理的；但 L 是否等於 NL、以及 L 是否嚴格小於 P，兩者都是著名的未解問題。一個常見的誤解：無向圖連通性（忽略箭頭方向，能否從 s 到 t？）長久以來被認為需要非確定性，但 Reingold 在 2004 年證明它屬於 L，這是個著名而困難的結果。相對地，有向可達性是 NL 的典範問題，且不已知屬於 L。