P41 · Log-space machine

🔊 Listen

1 · L · the smallest interesting space class

L (sometimes LOGSPACE) is the class of decision problems solvable by a deterministic TM using O(log n) work-tape space. By convention, the input tape is read-only and doesn't count toward the space bound — otherwise L would equal P trivially via length-n input storage.

Why log n is the right scale

log n bits is exactly enough to store an index into the input — a pointer to a tape cell. So L-algorithms are roughly "those that work with a constant number of pointers into the input plus a constant amount of additional state."

PALINDROME ∈ L

On input w of length n: maintain two pointers i = 0 and j = n − 1. While i < j: read w[i] and w[j], reject if they differ, else i++ and j--. Accept if loop completes.

Space used: two pointers (⌈log₂ n⌉ bits each) plus O(1) auxiliary state. Total: O(log n).

Other classic L problems: REACHABILITY in undirected graphs (Reingold 2008, a deep result), parity, comparison of two unary numbers, recognising regular languages.

🔊 Listen

2 · Animated demo · auto-plays · loops

🔊 Listen

3 · Pitfalls

Input tape free, work tape counted. A common confusion. If both counted, L = P trivially. The distinction makes L a meaningful subclass of P.
L ⊆ P. A LOGSPACE machine has at most |Q| · log n · |Γ|^{log n} = poly(n) configurations, so it can be simulated in polynomial time. So L is at most P.
Whether L = P is open. Whether L is properly contained in P is one of the famous open problems. Most believe L ⊊ P.

🔊 Listen

4 · Q&A defence notes

Q1. Why is the input tape "free"?
L is defined on a two-tape model: a read-only input tape and a work tape. Only the work tape counts toward the space bound. Otherwise L would equal P automatically (since reading length-n input requires Ω(n) "space" in the wrong sense).
Q2. Why do 2 pointers fit in O(log n) bits?
Each pointer is an integer in [0, n−1], encodable in ⌈log₂ n⌉ bits. Two pointers fit in 2 log n bits. Adding O(1) auxiliary state keeps us in O(log n).
Q3. What's the time complexity of the palindrome check?
O(n) — each character pair compared once. So PALINDROME is in L ⊆ P with linear time. The space class L is a refinement of polynomial time, not a separate sphere.
Q4. What's the relationship to NL?
L ⊆ NL — deterministic LOGSPACE is contained in nondeterministic LOGSPACE. Whether L = NL is open.

🔊 Listen

5 · Where to read more

Sipser: §8.4 (definitions of L and NL), examples. Lecture notes: Module 7 slide 1. Companion problems: P42 (NL-PATH), P43 (PATH is NL-complete), P44 (inductive counting).