the class L
L is the club of problems you can solve while remembering almost nothing: just a fixed handful of pointers and counters, no matter how big the input gets. Imagine an auditor who must check a giant ledger but is allowed only a few sticky notes. They cannot photocopy the ledger; they can only flip back and forth, jotting a position here, a tally there. The tasks such a memory-starved auditor can still finish are exactly the problems in L.
Formally, L equals SPACE(log n): the set of languages decided by a deterministic Turing machine that uses O(log n) work-tape cells on inputs of length n, with the input itself sitting on a separate read-only tape. The L stands for logarithmic. Because O(log n) bits encode only a constant number of indices into the input, an L-machine processes its data by re-scanning the read-only tape over and over, never building up a large memory of its own. Many bread-and-butter operations live here: deciding divisibility, comparing or adding numbers, checking that brackets match, recognizing simple patterns.
L matters as the bottom rung we can clearly stand on, and as the deterministic counterpart of NL. We know L is contained in NL is contained in P, so anything in L is also tractable in time; but whether L equals NL, and whether L is strictly smaller than P, are both famous OPEN questions. A frequent misconception: undirected graph connectivity (can you get from s to t ignoring arrow directions?) was long thought to need nondeterminism, but Reingold proved in 2004 that it is in L, a celebrated and hard result. Directed reachability, by contrast, is the canonical NL problem and is not known to be in L.
Checking whether a string of brackets like ((())) is balanced is in L: keep one counter for how many opens are still unmatched, increment on '(' and decrement on ')', reject if it ever goes negative, accept if it ends at zero. The counter never exceeds n, so it needs only O(log n) cells.
L is deterministic log space: solve it with a constant number of O(log n)-bit counters and pointers.
Whether L = NL and whether L is strictly inside P are both OPEN. We know L is contained in NL is contained in P, but no separation among these three has been proved.