An algorithm can reuse memory after a calculation finishes, whereas time already spent cannot be recovered. Space complexity measures this reusable resource. A small-space machine can still run for a long time, and the difference is visible in graph reachability.
Why space needs its own accounting
In the earlier units, the central resource was the number of computational steps. Time is a cumulative resource: every step taken is permanently charged to the computation. Memory behaves differently. A cell of the work tape that held an intermediate value can be overwritten, so the same few cells may serve thousands of successive subcalculations. A procedure that looks expensive when we count the steps it executes may therefore be modest when we count the distinct storage it needs at any one moment.
This unit has three goals. The first is to fix a model of space that is meaningful even below linear size, which requires a careful convention about the input. The second is to show that the basic problem of deciding whether one vertex of a directed graph can reach another is solvable by a nondeterministic machine with only logarithmic work space. The third is to relate space to time and to deterministic space: we prove that nondeterministic logarithmic space is contained in polynomial time, and state the deterministic logarithm-squared space bound for reachability, whose proof is in a separate continuation. The proofs rely on a single idea that recurs throughout the unit, namely that a machine with little memory can be in only a small number of distinct situations, and that this limitation can be counted exactly.
Graph reachability is the right test case for three reasons. It is a natural problem with a clean definition. Its obvious algorithms, such as breadth-first search, use a marking array that costs space linear in the number of vertices, so the logarithmic bound is a genuine improvement rather than a bookkeeping trick. And it is expressive enough that, as noted below, it captures the whole class .
Measuring space
Definition 3.1.1
(Space classes)
Use a read-only input tape and a separate read-write work tape; space is the number of work-tape cells visited. is the class of languages decided by deterministic machines using work space on inputs of length . is the analogous nondeterministic class: a yes-input has at least one accepting branch, a no-input has none, and all branches obey the space bound. is the union of deterministic polynomial-space classes.
The read-only convention matters: charging the entire input tape would already cost cells and make a logarithmic bound impossible for ordinary inputs. A work-tape counter can still address an input position using bits. When discussing nondeterministic machines here, require all branches to halt, which is achieved in the reachability algorithm below by explicitly bounding its number of steps.
It is worth being explicit about what the convention permits. The machine may move its input head freely in both directions, read the symbol under the head, and rescan the input as often as it likes. It may not write on the input tape. Consequently the only way to remember anything about the input is to write it on the work tape or to leave the input head at a position that encodes it. Storing a position between and costs bits, which is why a logarithmic work tape is exactly large enough to hold a constant number of pointers into the input, or a constant number of numbers of size polynomial in . This is the working intuition for : a log-space machine is a finite controller equipped with a fixed number of pointers and counters.
Reachability by guessing a path
Proposition 3.1.2
(Directed reachability is in NL)
Given a directed graph with vertices and specified vertices , deciding whether a directed path from to exists is in under standard explicit graph encodings.
Proof
(Guessing a simple path with a counter)
If is reachable, a simple path has at most edges: remove cycles from any walk. Store the current vertex and a counter, each in bits. Starting at , nondeterministically choose a vertex, scan the read-only input to check that the chosen edge exists, and advance the counter. Accept if is reached; reject once edges have been tried. An accepting branch describes a real path, and a simple path supplies an accepting sequence of choices whenever one exists. All branches halt and use logarithmic work space.
Some details of this proof deserve to be made explicit. The case is covered because the machine tests whether the current vertex equals before any edge is taken, so the empty path of length is accepted. The edge check uses the explicit encoding, whether adjacency matrix or edge list, and requires a pointer into the input. The input has length polynomial in , so such a pointer needs bits. Finally, the guessed vertex is written on the work tape before the check, which costs one more register of bits. In total the machine keeps a constant number of registers of logarithmic size.
Completeness and Savitch's theorem
Directed reachability is NL-complete under logarithmic-space many-one reductions, as proved in the reachability-completeness continuation. Savitch's theorem, proved in the companion note on Savitch's theorem, says that for space-constructible , nondeterministic space is contained in deterministic space . Consequently , and nondeterministic polynomial space equals . These inclusions do not establish , which remains open.
Completeness transfers reachability results to every language in NL; the reachability-completeness continuation constructs the reduction in logarithmic work space and gives the square-logarithmic algorithm. The companion note proves both the general Savitch theorem and the output-tape simulation used to compose a log-space reduction with the reachability algorithm.
A bounded search
Worked example 3.1.3
(Cycles do not require an unbounded search)
Suppose the graph has edges , , and . The machine may guess the loop , but its counter forces that branch to reject after the prescribed number of edges. Another branch guesses and accepts. Nondeterministic acceptance requires one accepting branch, not that every choice succeeds.
Common mistake
(Space and time are different resources)
A logarithmic-space algorithm is not defined by a logarithmic number of steps. It may repeatedly scan the input, reusing the same few work cells. Conversely, storing all visited vertices explicitly can take linear or greater space even though it makes graph search straightforward.
Configurations and the polynomial-time ceiling
A machine with little memory can be in only a few different situations, and this can be counted. The following definition makes the idea precise.
Definition 3.1.4
(Configuration and configuration graph)
Fix a machine with state set and work alphabet , and an input of length . Assume the input is delimited by endmarkers, so the input head has possible positions. Suppose every branch of on uses at most work cells. A configuration is a tuple consisting of the current state, the input-head position, the work-head position (an integer from to ), and the contents of the work cells. The configuration graph has these configurations as vertices, with an edge from to exactly when the transition rules of , applied to the input symbol under the input head in , allow as a successor of in one step.
The number of vertices of is at most , because each component can be chosen independently. If for a constant , then , which is a polynomial in since and are constants. Hence the configuration graph has polynomially many vertices. This is the fundamental difference between logarithmic and polynomial space: with the same count gives , which is exponential.
Theorem 3.1.5
(Logarithmic space lies inside polynomial time)
Let be a nondeterministic machine with a read-only input tape such that, on every input of length , every branch halts and uses at most work cells for some constant . Then the language decided by is decidable by a deterministic algorithm in time polynomial in . Consequently .
Proof
(Counting configurations and searching the graph)
Fix an input of length and write ; in particular . The number of configurations is at most , which is bounded by a polynomial in as computed above. A deterministic algorithm proceeds as follows. First, enumerate all candidate configurations. Second, for every ordered pair , decide whether is a legal one-step successor of , which requires reading one input symbol and consulting the finite transition table, so it takes time polynomial in at worst. Third, run breadth-first search in from the initial configuration and accept exactly when some accepting configuration is reached.
For correctness, a sequence of configurations from the initial one to an accepting one, each step respecting the transition rules, is precisely an accepting branch of on ; conversely, every accepting branch is such a path. The total time is at most pair tests, each polynomial, plus a search taking time , so it is polynomial in . The inclusion holds because a deterministic machine is a nondeterministic machine with a single choice at each step, and the inclusion follows because the argument applies to any machine of the stated kind.
Proof X-ray
Where the space bound enters the polynomial-time argument
The proof moves the question from computations to a graph, and it uses the space bound in exactly one place: to count the vertices. Writing configurations as tuples makes the count a product of independent choices, and logarithmic turns the factor into a polynomial. The algorithm itself is a plain search of a polynomial-size graph; it stores the whole graph and its marks, so it is a polynomial-time procedure and not a logarithmic-space one. With the same count is , and the argument yields only an exponential bound. The correctness direction needs nothing about the bound: accepting branches correspond exactly to paths from the initial configuration to an accepting one.
Notice that this proof reduces an arbitrary computation to a reachability question on a polynomial-size graph, and then solves that question in polynomial time. This is precisely the mechanism behind the NL-completeness of reachability proved in the separate reachability-completeness continuation. This proof stores the graph and search marks and therefore is a polynomial-time procedure, not a logarithmic-space construction. Output length is not itself the obstacle because a log-space reduction may use a write-only output tape; a log-space construction generates and tests candidate configuration pairs on demand.
Further worked examples
Worked example 3.1.6
(Counting configurations for a concrete machine)
Suppose a deterministic machine has states and a binary work alphabet (counting the blank as one of the two symbols, so ). On inputs of length it is promised to use at most work cells; note that , so . The bound on the number of configurations is
First, . Next, . Finally, . So there are at most about forty-one million configurations. This number is much larger than but is still a polynomial-size set. By contrast, if the machine were allowed cells, the factor alone would exceed . If the deterministic machine halts, it does so in fewer than steps; if a configuration repeats, determinism makes it loop forever.
Worked example 3.1.7
(Running the guess-and-check machine on a five-vertex graph)
Let the vertices be and the edges , , , , , with . Each vertex name needs bits, and the edge counter ranges over , which also needs bits. Consider the query , . One branch guesses and checks the edge by scanning the input, then guesses , then guesses ; after three edges the current vertex equals and the branch accepts. A different branch guesses : after four edges, which is , the current vertex is and the counter bound forces rejection. Since an accepting branch exists, the input is accepted.
Now consider , . The vertices reachable from are exactly , since vertex has no incoming edge. Every branch either guesses a non-edge and rejects at the edge check, or follows legitimate edges inside this set and eventually exhausts the counter. No branch ever reaches , so there is no accepting branch and the input is rejected. In both queries the machine stores a current vertex, a guess, and a counter, which is bits plus the bits for an input pointer.
Practice and solutions
Quick check
(Why can a reachable target always be reached by a path of at most edges?)
Solution · Answer
From any finite walk to the target, remove the segment between two occurrences of a repeated vertex. Repeating this produces a walk with no repeated vertex, hence at most edges.
Quick check
(Why is ?)
Solution · Answer
A deterministic logarithmic-space machine is a nondeterministic machine with only one possible next move at each step, so it meets the same space and acceptance requirements.
Further practice and solutions
Quick check
(A deterministic machine has states and a binary work alphabet, and uses at most work cells on inputs of length (note ). Bound its number of configurations.)
Solution · Answer
The bound is . We have , then , then . So there are at most configurations.
Quick check
(Let with edges , , , . Decide whether vertex is reachable from vertex , and explain what the guess-and-check machine does.)
Solution · Answer
The vertices reachable from are , then , then , then , giving the set . The edge points into and gives a way to leave , not to arrive at it, and no edge ends at . Hence is not reachable. Every branch of the machine, starting at , either fails an edge check or follows edges within until the counter reaches , and rejects. No branch accepts, so the answer is no.
Quick check
(Describe a logarithmic-space algorithm for the language of strings with .)
Solution · Answer
First scan the input once with a finite-state check that it has the form , rejecting otherwise. During a second scan keep a binary counter for the number of s, which never exceeds and so needs bits. On a third scan keep a second counter for the number of s. Accept exactly when the two counters are equal. Only two counters and a constant number of control states are used, so the work space is .
Quick check
(Prove directly that a deterministic machine which halts on every input and uses at most work cells on inputs of length runs in polynomially many steps.)
Solution · Answer
Let be the number of configurations, which is polynomial by the counting bound. A deterministic machine that halts never visits the same configuration twice: a repeated configuration would force the computation to cycle forever, since the next configuration is determined. So the number of steps is less than , which is polynomial.
Quick check
(In a graph containing the walk , produce a shorter walk by the cycle-removal argument, and say how many edges are saved.)
Solution · Answer
The vertex occurs at positions and (counting from ). Deleting the portion between them (the vertices and and one copy of ) gives the walk . The original walk has edges and the new one has , so edges are saved. The edge used in the new walk comes from the original walk, so it exists in the graph.