Logrymden

Logrymden, or logarithmic space, is a concept in theoretical computer science that describes the amount of memory a computation uses that grows at most logarithmically with the input size n. In formal models such as Turing machines, a machine operating in logrymden uses O(log n) cells on its work tape (in addition to reading the input itself), which means the memory footprint increases very slowly as the input grows.

Two central complexity classes are defined in this setting: L (deterministic logrymden) and NL (nondeterministic logrymden). A problem lies in L if it can be decided by a deterministic machine using logarithmic space; NL contains problems solvable by a nondeterministic log-space machine. It is known that L ⊆ NL ⊆ P, but whether NL equals L is an open question in complexity theory. Savitch's theorem states that NSPACE(s(n)) ⊆ DSPACE((s(n))^2), so for s(n) = log n, NL ⊆ DSPACE((log n)^2).

Many natural problems are NL-complete under logarithmic-space reductions, meaning they are among the hardest problems in NL with respect to such reductions. A canonical example is the ST-connectivity (reachability) problem in directed graphs, where determining whether there exists a path from a given source to a target can be used to simulate any NL problem under logspace reductions.

Logrymden is primarily a theoretical measure but informs the design and analysis of memory-efficient algorithms and models, including certain graph and automata problems. It contrasts with time-based measures and helps clarify what can be computed under strict memory constraints.