NL 類（class NL）
NL 是多了一項超能力的 L：機器可以猜測。再想像我們那位記憶力受限的稽核員，仍只獲准用幾張便利貼，但現在允許他在每個岔路口對該往哪走做幸運的猜測，只要存在某串幸運猜測能抵達目標即可。他不必有系統地找出正確路徑；他只需能用那本小筆記本一步步驗證所猜的路徑。NL 就是能以這種方式解決的問題家族。
形式上，NL 等於 NSPACE(log n)：能被一台用 O(log n) 工作空間的非確定型圖靈機接受的語言，其中只要至少有一條所猜的計算路徑導向接受狀態，機器就接受該輸入。關鍵的紀律是每個猜測都必須能在對數空間內即時被檢查，所以機器在探索時只能握有常數個指標。看 NL 運作的教科書範例是有向圖可達性：要測試是否存在從 s 到 t 的路徑，機器只記住目前的頂點（一個指標，O(log n) 位元），並反覆猜測下一條要走的邊，從不儲存走過的路徑。
NL 恰好位於 L 之上、P 之下：L 包含於 NL 包含於 P，三個包含關係都被相信是嚴格的，卻無一被證明。兩個里程碑事實使 NL 與眾不同。由 Savitch 定理，NL 包含於 SPACE((log n)^2)，所以這種非確定性只花確定型空間的平方擠壓。由 Immerman-Szelepcsenyi 定理，NL 等於 co-NL：非確定型對數空間對補集封閉，而時間受限的非確定性並不已知如此。一個常見誤解是這裡的非確定性意味隨機或真正的平行硬體；兩者皆非，它只是「是否存在某條接受性猜測」的數學裝置。
要判定有向可達性（PATH）：給定一張圖與頂點 s、t，只儲存目前頂點（起始設為 s）。反覆猜測一條出邊並沿它移動，同時遞減一個上限為頂點數的步數計數器。若曾抵達 t 就接受。只保留一個頂點指標與一個計數器，所以這在 O(log n) 空間內執行。
NL 是非確定型對數空間；一次猜一個頂點地猜出一條路徑，即可判定有向可達性。
NL 中的非確定性不是隨機，也不是額外硬體；它是「存在某條接受性猜測」的數學裝置。而由 Immerman-Szelepcsenyi，NL = co-NL，與時間受限情形不同（那裡 NP = co-NP 仍未解）。