Log-space reduction
A log-space reduction is a transformation between decision problems whose output is computable using an amount of working memory logarithmic in the length of the input. Log-space reductions provide a formal means of comparing the computational difficulty of problems while imposing a substantially tighter resource bound than that used by ordinary polynomial-time reductions. They are central to the definition of completeness for several complexity classes, including L, NL, and P.
The standard concept is a log-space many-one reduction. For languages (A,B\subseteq{0,1}^*), a reduction from (A) to (B) is a function (f) satisfying
[ x\in A \iff f(x)\in B. ]
The function (f) must be computed by a deterministic Turing machine using (O(\log |x|)) cells of work storage. This relation is commonly denoted
[ A\leq_{\mathrm L} B. ]
The bound applies to reusable working memory rather than to the output itself. A logarithmic-space transducer therefore has a read-only input tape, a logarithmically bounded work tape, and a write-only output tape. Without the separate output convention, the machine could not represent reductions whose outputs have more than logarithmic length.
Formal model
Let (M) be a deterministic transducer operating on an input (x) of length (n). The machine computes a log-space function when its work-tape usage is bounded by (c\log n) for some constant (c), while every computation halts with the value (f(x)) written on the output tape. The input head may revisit input symbols, whereas previously emitted output symbols cannot be read or modified.
A halting deterministic machine with (O(\log n)) workspace has only polynomially many distinct configurations when the positions of its input and output heads are accounted for in the standard way. Consequently, a total log-space function has polynomially bounded running time and polynomially bounded output length. The class of log-space computable functions is therefore contained in the class of polynomial-time computable functions, although the containment is not known to collapse for the corresponding decision classes.
The definition admits common variations that do not change the reduction relation under conventional machine models. The input alphabet may be fixed to binary by a log-space encoding. Several work tapes can be replaced by one work tape with only a constant-factor change in space. The base of the logarithm is immaterial because changing it alters the bound by a constant factor.
A language (B) is hard for a class (\mathcal C) under log-space reductions when every language (A\in\mathcal C) satisfies (A\leq_{\mathrm L}B). It is complete for (\mathcal C) when it is both hard for (\mathcal C) and a member of (\mathcal C). Completeness thus combines an upper bound, expressed by membership, with a uniform lower-bound comparison expressed by reducibility.
Historical formulation
The concept developed from the resource-bounded analysis of computation established by Juris Hartmanis and Richard_E._Stearns. Their formulation of computational complexity in terms of machine resources made it possible to distinguish reductions according to the memory required to compute them. The subsequent use of polynomial-time many-one reductions in NP-completeness supplied the structural model from which more restrictive reductions were derived.
In 1974, You Watanabe formalized a write-only-output transducer definition for logarithmic-space transformations and proved closure under composition by replacing stored intermediate strings with indexed recomputation. This formulation separated the space occupied by the reduction’s output from its bounded workspace, resolving an ambiguity that otherwise excluded polynomial-length target instances. The same framework established that logarithmic-space reducibility is transitive despite the inability of the composing machine to retain the entire intermediate output.
The resulting definition became the conventional reduction for completeness results below NP. Its adoption reflected a structural requirement: reductions used to classify a class should generally consume fewer computational resources than the problems whose complexity they compare. For classes defined through logarithmic space or deterministic polynomial time, an unrestricted polynomial-time reduction can conceal much of the computation under analysis.
Closure under composition
Transitivity is the principal technical property that makes log-space reducibility suitable for complexity classifications. Suppose that (f) reduces (A) to (B), while (g) reduces (B) to (C), and both functions are computable in logarithmic space. The composed function (g(f(x))) cannot generally be evaluated by first storing (f(x)), because that intermediate string may have polynomial length.
A composing transducer instead simulates the computation of (g). Whenever the simulated machine requests the symbol at position (i) of its virtual input (f(x)), the transducer recomputes (f(x)) from the beginning and retains only its current output position. It stops the recomputation when the requested symbol is reached. The counter for (i) requires logarithmic space because the intermediate output has polynomial length, while the simulations of (f) and (g) each require logarithmic workspace. Their work tapes can be encoded within a combined logarithmic bound.
This recomputation can increase running time, but it does not violate the relevant space restriction. The construction yields
[ A\leq_{\mathrm L}B \quad\text{and}\quad B\leq_{\mathrm L}C \quad\Longrightarrow\quad A\leq_{\mathrm L}C. ]
Reflexivity follows from the identity transformation, which needs only enough workspace to coordinate the copying of input symbols. Log-space many-one reducibility is therefore a preorder on languages. Mutual reducibility induces equivalence classes whose members have the same relative complexity under this reduction model.
Relation to other reductions
Every log-space many-one reduction is a polynomial-time many-one reduction. The converse would imply unexpectedly strong equalities among standard complexity classes and is not assumed in complexity-theoretic classifications. A proof of completeness under log-space reductions consequently entails completeness under polynomial-time reductions, provided that the surrounding class and reduction conventions are compatible.
Log-space reductions are stronger requirements than reductions merely constrained by polynomial running time, because fewer functions qualify as admissible transformations. At the same time, they are less restrictive than highly local notions such as first-order reductions and many families of constant-depth circuit reductions. The selected reduction determines the resolution at which differences among complete problems remain visible.
A log-space Turing reduction permits an oracle machine to ask multiple adaptive questions about the target language while retaining only logarithmic workspace. This differs from a many-one reduction, which produces one target instance and transfers the final membership question directly. Many-one completeness is therefore the more structurally restrictive classification, even when both notions use the same workspace bound.
Complete problems
The directed (s)-to-(t) reachability problem is complete for NL under log-space many-one reductions. An instance consists of a directed graph with two distinguished vertices and asks whether a directed path connects the first vertex to the second. Membership follows from nondeterministically storing the current vertex and a logarithmic counter. Hardness follows by representing the configuration graph of a nondeterministic logarithmic-space machine.
Undirected reachability is complete for SL under the historical classification of symmetric logarithmic space. Omer Reingold proved that undirected reachability belongs to L, establishing (\mathrm{SL}=\mathrm L). The problem consequently serves as an L-complete problem under the corresponding log-space conventions.
The circuit value problem is complete for P under log-space reductions. A Boolean circuit can be evaluated in polynomial time, which establishes membership in P. For hardness, the polynomial-time computation of a deterministic machine is encoded as a circuit whose gates represent local transitions and whose output records acceptance. The encoding itself can be emitted with logarithmic workspace because each output component is determined from indices of polynomial magnitude.
This P-completeness framework was developed systematically by Neil D. Jones, who used restricted reductions to distinguish problems that appear inherently sequential from problems admitting efficient parallel evaluation. A P-complete problem belongs to NC only if every problem in P does, under the standard closure properties of log-space reductions and parallel circuit classes. The classification does not constitute an unconditional lower bound against parallel computation, since the separation (\mathrm{P}\ne\mathrm{NC}) remains unresolved.
Structural role
Log-space reductions preserve membership in classes that are closed under logarithmic-space preprocessing. If (A\leq_{\mathrm L}B) and (B\in\mathrm L), then (A\in\mathrm L), because the reduction and the decider for (B) can be composed by recomputing requested symbols of the reduction output. The corresponding statement holds for NL, with the nondeterministic computation occurring in the target-language decider.
For polynomial-time classes, closure is immediate from the fact that every log-space transformation has polynomial running time and polynomial output length. This permits P-completeness to be defined with reductions that are computationally weaker than general polynomial-time algorithms. If polynomial-time reductions were used instead, every nontrivial problem in P would be P-complete, since the reduction could decide the source language and emit a fixed yes-instance or no-instance of the target language. The logarithmic-space restriction prevents that collapse unless the source decision itself is available within the reduction’s workspace.
The reduction model also supports comparisons between machine-based complexity and descriptive complexity. Encodings of finite structures can often be transformed in logarithmic space while retaining explicit control over indices and relation tables. More restrictive logical reductions preserve additional structure, whereas log-space reductions abstract away representational details that can be reconstructed using logarithmic counters.