Space Complexity

Space-bounded computation, reachability in configuration graphs, and Savitch's theorem.

Goals

• Define deterministic and nondeterministic space with read-only input.
• Use configuration graphs to prove membership and completeness.
• Compose log-space reductions without storing their output.
• Derive Savitch's recursion and its full space bound.
• Explain $\mathrm{NL}=\mathrm{coNL}$ and $\mathrm{NPSPACE}=\mathrm{PSPACE}$ without overstating their proofs.

1. The model and what is counted

A space-bounded multitape Turing machine has a read-only input tape and one or more read/write work tapes. Input-head position is not charged as work space; work-tape cells ever visited are. Output for a transducer is write-only, so it cannot be used as free memory.

A nondeterministic decider must halt on every branch and use the bound on every branch. Space differs from time because cells can be reused: a polynomial-space computation may run for exponential time. For conventional machines with $s(n)\ge\log n$, repeated configurations can be removed from any shortest accepting path, so a halting search need not exceed the number of configurations.

2. Configuration graphs

A configuration records the finite control state, input-head position, work-tape contents in the used region, and work-head positions. For fixed alphabet and state set, an $s(n)$-space machine has

configurations when $s(n)\ge\log n$. Its directed configuration graph has one vertex per legal configuration and an edge for one valid transition. The machine accepts exactly when an accepting configuration is reachable from the start configuration.

This graph is normally implicit. A simulator generates a requested configuration or checks adjacency using $O(s(n))$ space; writing all exponentially many vertices would destroy the bound.

3. STCON is the canonical NL problem

STCON (directed $s$-$t$ connectivity) asks whether a directed graph has a path from designated $s$ to $t$.

Membership in NL. Store the current vertex $v$ and a counter up to $|V|$. Nondeterministically guess a next vertex, verify that the edge exists, and accept on reaching $t$. A simple path has length at most $|V|-1$, so the counter prevents endless branches. Both vertex and counter use $O(\log|V|)$ bits.

NL-hardness. Let $A\in\mathrm{NL}$ be decided by machine $M$. Map input $x$ to the configuration graph $G_{M,x}$ with its start and accepting configurations. Acceptance is reachability. The reduction cannot print the whole graph from memory, but a log-space transducer can enumerate configuration names and edge pairs using $O(\log |x|)$ counters, recomputing each local transition. Since configurations of a log-space machine have $O(\log n)$ bits, this is a log-space many-one reduction. Therefore STCON is NL-complete.

4. Log-space reductions and composition

$A\le_m^{\mathrm L}B$ means a deterministic log-space transducer computes $f$ such that

with polynomially bounded output length. Such a transducer runs in polynomial time: once its work configuration and output position repeat without progress, it loops, which a total transducer cannot do.

The subtle point in composing $f$ and $g$ is that $f(x)$ may be polynomially long and cannot be stored. To compute an output bit of $g(f(x))$, simulate $g$. Whenever it asks for the $i$th input symbol, rerun the transducer for $f$ from the start with an $O(\log n)$ counter until symbol $i$ is produced. Store only $g$'s $O(\log n)$ work configuration, $i$, and $f$'s current work configuration. Polynomial output lengths imply $\log|f(x)|=O(\log n)$. Thus log-space reductions compose by recomputation.

Consequently, to prove $B$ NL-complete, show $B\in\mathrm{NL}$ and reduce a known NL-complete problem—usually STCON—to $B$. A polynomial-time reduction is not enough for NL-completeness.

5. Savitch's theorem: full recursion

Savitch's theorem. For space-constructible $s(n)\ge\log n$, $\mathrm{NSPACE}(s(n))\subseteq\mathrm{DSPACE}(s(n)^2).$

Let $M$ use $O(s)$ nondeterministic space and have at most $N=2^{c s}$ configurations. Define

Base case $\ell=0$: accept iff $u=v$ or $(u,v)$ is one transition. For $\ell>0$, enumerate every configuration $m$ and accept if both

accept. Correctness follows by splitting a path of length at most $2^\ell$ at its midpoint; conversely, concatenating the two recursive paths gives a path of the allowed length.

Call with $\ell=\lceil\log N\rceil=O(s)$. At one recursion level store $u,v,m$, $\ell$, and an enumeration counter: $O(s)$ bits. The two recursive calls are made sequentially, and midpoint work space is reused. Therefore

Time is enormous: roughly $N^{O(\log N)}=2^{O(s^2)}$. That is acceptable because the theorem claims space, not time. Multiplying by the recursion's branching factor is a time analysis, not a space analysis.

For $s(n)=n^k$, Savitch gives

The reverse inclusion is immediate because deterministic choice is a special case of nondeterminism. Hence

This equality is a direct corollary of Savitch; it is not known whether the analogous logarithmic inclusion collapses to $\mathrm L=\mathrm{NL}$, because Savitch only yields $\mathrm{NL}\subseteq\mathrm{SPACE}(\log^2 n)$.

6. The complement theorem

Immerman–Szelepcsényi theorem. $\mathrm{NL}=\mathrm{coNL}$; more generally, $\mathrm{NSPACE}(s(n))$ is closed under complement for $s(n)\ge\log n$.

The statement is examinable; the full inductive-counting proof is longer than Savitch's proof. Its key idea is to certify nonreachability without listing all reached vertices. Let $R_i$ be vertices reachable from $s$ in at most $i$ steps. Nondeterministically verify the count $|R_i|$ from $|R_{i-1}|$ by scanning all vertices and using reachability witnesses of length $i-1$. Once the exact count of reachable vertices is certified, verify that $t$ is not among them. Counters and one vertex name require only logarithmic space.

The surprising point is that nondeterminism can certify a universal-looking negative fact by first certifying an exact count. A mere statement “guess that no path exists” proves nothing.

Worked example

Consider vertices $1,2,3,4$ and edges $1\to2$, $2\to3$, $1\to4$. The NL STCON machine may guess $1,2,3$ to accept $(1,3)$. It stores only the current name and a counter, not the path. For Savitch on the same graph with length bound four, try midpoint $m=2$: recursively establish a path $1\leadsto2$ of length at most two and $2\leadsto3$ of length at most two. Failed midpoint attempts are discarded before trying the next.

For a reduction-composition example, suppose $f(x)$ outputs an adjacency matrix and $g$ reads its entries in arbitrary order. The composition does not cache that matrix. Each request for entry $i$ reruns $f$ until its $i$th output symbol. Time increases, but work space stays logarithmic.

Common mistakes

• Charging the read-only input tape as work space, or using write-only output as memory.
• Omitting the step counter in the NL algorithm, leaving nonhalting branches.
• Materializing the configuration graph.
• Using a polynomial-time reduction where log-space completeness is required.
• Storing $f(x)$ while claiming closure of log-space reductions.
• Multiplying Savitch's recursive branches into a space bound.
• Claiming Savitch proves $\mathrm L=\mathrm{NL}$.
• Treating $\mathrm{NL}=\mathrm{coNL}$ as obvious from swapping accepting states.

Visualizations

Draw two views of the same computation: an implicit configuration graph and the depth-first Savitch recursion. Show only one active recursive path in memory. A second panel can depict composition as an on-demand wire: $g$ requests position $i$, and $f$ is replayed to regenerate it.

Exercises

Exercise 1 — Short accepting path

Prove that a simple accepting path of a space-$s(n)$ machine uses fewer than $N$ configurations, where $N$ is the configuration count.

Exercise 2 — What an NL STCON machine stores

Describe the work state of a standard NL machine for STCON and bound space by $O(\log|V|)$.

Exercise 3 — Composing log-space reductions

Why is $\log|f(x)|=O(\log|x|)$ essential in composition? What is recomputed instead of stored?

Exercise 4 — Savitch to $O(s^2)$

Solve $S(\ell)=S(\ell-1)+O(s)$ at depth $\ell=O(s)$, and deduce Savitch's space bound.

Exercise 5 — $\mathrm{NPSPACE}=\mathrm{PSPACE}$ and NL=coNL

Deduce $\mathrm{NPSPACE}=\mathrm{PSPACE}$ from Savitch. Does $\mathrm{NL}=\mathrm{coNL}$ imply $\mathrm L=\mathrm{NL}$?

Summary

Space is understood via implicit reachability. STCON captures NL; Savitch squares space; NPSPACE=PSPACE; Immerman–Szelepcsényi yields NL=coNL.

Guided practice

Task 1 — Configuration count in log space

Prove that an $O(\log n)$-space machine has polynomially many configurations.

Task 2 — Complete versus hard

Distinguish NL-hard from NL-complete. When does a reduction to STCON prove completeness?

Task 3 — Immerman–Szelepcsényi sketch

Outline at idea level why undirected-style non-reachability for STCON lies in NL (no full proof).

Source trail and authority

• Student/course evidence: סיכומי שיעור/סיכום ממוזג.pdf, pp. 101–130 and p. 142 (L/NL, reachability, reductions, Savitch, and complement material). This is a merged student summary used for course alignment, not theorem authority.
• Textbook authority: Sipser, 3rd ed., Ch. 8: §8.1 pp. 333–336 (Savitch), §§8.4–8.5 pp. 348–354 (L/NL and NL-completeness), §8.6 pp. 354–356 (NL=coNL); Arora–Barak draft, Ch. 4, §§4.1–4.4, book pp. 75–87; Papadimitriou, Ch. 7, especially §7.3 pp. 146–154, and Ch. 16 §16.1 pp. 395–399.
• Editorial status: all stated class equalities and the Savitch recurrence were checked against these sections. The NL=coNL proof is explicitly a proof sketch. Reviewed; high confidence.