Space complexity

The space complexity of an algorithm measures the maximum working storage used during its computation as a function of encoded input length. A machine-level definition must state which storage counts. In a common Turing machine convention, a read-only input tape and a write-only output tape are excluded, while visited work-tape cells are counted.

For example, count the ones in a binary string of length $n$ by scanning once and retaining a binary counter. Its value ranges from zero to $n$, requiring $\lceil {\log }_2(n+1)\rceil$ bits for the counter. Keeping a separate copy of the full input would instead require $n$ bits. The computation can therefore use much less working storage than the amount of data it examines.

The maximum concerns simultaneously retained storage, not the total amount allocated and later reused over time. Bit complexity and a unit-cost model also need care here: treating an arbitrarily large integer as one storage cell can hide its growing representation size.

A constant space algorithm uses $O(1)$ working storage with respect to the stated input-size parameter. Under a machine-word model, an iterative binary search needs only a fixed number of indices, so it uses constant auxiliary words. Under a bit model, indices up to $n$ require $\Theta (\log n)$ bits, so constant words need not mean constant bits. Input and output storage may be excluded by an auxiliary-space convention, which must be stated. Keeping a fixed number of arbitrarily large integers is not a constant-bit-space guarantee.

An algorithm uses polynomial space if its working memory is bounded by a fixed polynomial in the input length. Exponentially many possibilities can still be searched when each candidate and the search counter need polynomial space and storage is reused. The decision problems with deterministic polynomial-space algorithms form PSPACE.

Languages accepted by Nondeterministic Turing machines using $O(s(n))$ work space on every computation path, with acceptance defined by existence of an accepting path. Bounded-space loops do not prevent the reachability interpretation in the finite configuration graph.

Reachability within $2^k$ steps can be tested by enumerating a midpoint and recursively testing two half-paths. Configurations have $O(s)$ bits and recursion depth $O(s)$, yielding deterministic space $O(s^2)$. The space-bound discovery by exit reachability permits this simulation without assuming that the supplied function $s$ is constructible.

For a bounded-space machine, start with a logarithmic work budget and test accepting reachability and reachability of a transition leaving the budget. Accept if acceptance is found, double the budget if an exit is reachable, and otherwise reject. If all paths use at most $Cs(n)$ space, doubling stops at $O(s(n))$. Each budget test uses the Savitch theorem recursion and the storage is reused. The method discovers a sufficient bound without computing $s(n)$.

Languages decidable by deterministic Turing machines using $O(s(n))$ work-tape cells with a read-only input. Input-head addresses take $O(\log n)$ bits, while the input itself is not charged to work space. The definition does not require the bound to be computed by the deciding machine.

PSPACE consists of decision problems solvable using a polynomial amount of work space. Running time may be exponential. Enumerating all polynomial-length relation encodings and reusing working storage preserves this bound, as does complementation. In particular fixed-sentence second-order logic model checking lies in PSPACE.

A polynomial-register real-arithmetic computation stores polynomially many real numbers and may use arbitrarily many additions, subtractions and multiplications, with comparison tests for decisions. Register count does not bound precision or time. Fixed gate constants or sufficiently accurate computable approximations must be specified. This resource model is distinct from ordinary bit-cost computation.

A logarithmic-space computation uses $O(\log n)$ work-tape cells on inputs of length $n$.

For canonical positive binary numeral system inputs, a logspace transducer can emit the canonical representation of their sum most significant digit first. Count the operand lengths, compute the final arithmetic carry to determine output length, and then compute each requested result digit by restarting the least-significant-first column recurrence. Each pass uses only a fixed number of $O(\log n)$-bit indices and one arithmetic carry. The binary-addition carry invariant proves correctness. Logspace composition by recomputation consequently permits any L property of the resulting digit string, including being a binary palindrome, to be tested without storing the sum.

A deterministic Turing machine with read-only input, $O(\log (n+2))$ work space, and successive write-only output whose contents it cannot inspect. A transducer for a total function halts on every input. It has a polynomial number of internal Turing machine configurations, so a halting run emits only a polynomial number of symbols. The unreadable output position does not affect subsequent transitions.

A total function computed by a halting logspace transducer. Its output may be much longer than its work tapes. Logspace-computable functions compose using logspace composition by recomputation.

To simulate $g$ on the virtual input $f(x)$, store the simulated input-head position and rerun the logspace transducer for $f$ whenever an input symbol is requested. Count emitted symbols until the requested position is reached. The intermediate output has polynomial length, so its positions take $O(\log n)$ bits, and the work space of $g$ is also $O(\log n)$. Storage used by successive recomputations is reused. This proves closure of logspace-computable functions under composition and transitivity of logspace many-one reductions.

$\mathbf{L}$ consists of decision problems solvable by a deterministic logarithmic space computation.

$\mathbf{NL}$ consists of decision problems solvable by a nondeterministic logarithmic space computation.

A decision problem is NL-complete when it belongs to NL and every problem in NL reduces to it by a deterministic logarithmic-space many-one reduction.

Decide whether a directed graph has a nonempty directed cycle; self-loops count. This problem is NL-complete. Membership guesses a returning walk of at most the vertex count. For hardness, layer a reachability instance into $N+1$ layers with wait arcs, then add only the backward edge from the target in the last layer to the source in the first. The otherwise acyclic layering has a cycle exactly when the original target is reachable. Zero-length paths must not be treated as cycles.

The directed ST-connectivity problem asks whether a directed graph contains a graph path from specified vertices $s$ to $t$. A zero-length graph path is permitted, so $s=t$ is a positive instance. It is NL-complete under logspace many-one reductions.

For membership in NL, guess a graph path of at most $N-1$ edges, where $N$ is the number of vertices. Retain only the current vertex and a step counter. A reachable target has a simple graph path within that bound, and the stored indices use logarithmic space.

For hardness, take an NL machine on a fixed input and construct its configuration graph. Only polynomially many configurations are possible within the workspace bound, and all configurations and local transition edges can be enumerated with a logspace transducer. Add one target collecting the accepting configurations. The target is reachable from the initial configuration exactly when the original machine accepts. This translates any NL language into directed reachability while respecting the reduction's storage bound.

Decide whether a finite directed graph has an even-length directed walk from a specified source $s$ to a specified target $t$. Vertices may repeat and a zero-length walk is allowed. The NL-completeness proof uses the graph of pairs $(v,b)$ with $b\in \{0,1\}$ tracking integer parity: every original edge flips $b$, and acceptance means reaching $(t,0)$ from $(s,0)$. At most $2|V|-1$ steps are needed in the parity graph. For hardness, subdivide every edge of an ordinary reachability instance into two directed edges. Both constructions are computable by logspace transducers. Requiring a simple path in a graph in the original graph changes the question; deleting an odd closed portion need not preserve integer parity.

The configuration graph of a machine on a fixed input has one vertex for each machine configuration and a directed edge for each valid computation step.

$\mathbf{co}\text{-}\mathbf{NL}$ consists of complements of languages in NL.

The Immerman–Szelepcsényi theorem states that $\mathbf{NL}=\mathbf{co}\text{-}\mathbf{NL}$. Its proof uses inductive counting of reachable configurations.

Inductive counting certifies complete reachable sets while retaining only a count and a few vertex indices. For a directed graph with $N$ vertices and start $s$, let $R_k$ contain the vertices reachable in at most $k$ steps and write $r_k=|R_k|$.

Suppose the exact count $r_k$ is known. A nondeterministic computation can enumerate each vertex, guess which belong to $R_k$, and justify every positive guess by a path of length at most $k$. Requiring exactly $r_k$ justified vertices prevents omissions: false positives have no valid path certificate. To certify $v\notin R_{k+1}$, also check $v\ne s$ and that none of those enumerated vertices has an edge to $v$.

Starting from $r_0=1$, certify membership or nonmembership for each vertex and accumulate $r_{k+1}$. After $N-1$ stages every reachable vertex has been counted, since cycles can be removed from a reaching path. Loop counters and the current vertex use only logarithmic space; guessed paths are checked one edge at a time, and the full reachable set is never stored. This is the counting mechanism behind the Immerman–Szelepcsényi theorem.^[ref]