An NL machine solves graph reachability (ST-REACHABILITY) on an n-node graph by 'guessing' a path from s to t one node at a time. Why can this be done with only O(log n) workspace, even if the path visits O(n) nodes?
AThe NL machine compresses the path into a logarithmic representation using a hash function
BOnly the current node and a step counter need to be stored at any point — the full path is never written down, and both fit within O(log n) bits
CAn n-node graph always has a reachable path of at most log n steps, so the counter stays small
DNL machines are allowed to use polynomial space to store the path but only report a log-space-sized answer
At each step, the machine guesses the next node on the path (one of n possibilities, requiring log n bits to name), verifies it has an edge from the current node, then overwrites 'current node' with the new node — discarding the previous one. A step counter (also log n bits) tracks that the total path length doesn't exceed n. At no point is the accumulated path stored; only the current position and count are kept. This demonstrates the key insight about NL: it captures problems where a witness of polynomial length can be verified one piece at a time with only log-space bookkeeping, rather than requiring the full witness to be in memory.
Question 2 Multiple Choice
Savitch's theorem proves NL ⊆ SPACE(log² n). The proof converts a nondeterministic log-space computation to a deterministic one. What is the core resource trade-off that makes this work?
AThe deterministic simulation is faster than the nondeterministic one, freeing up the space that would have been used for the time overhead
BThe deterministic simulation uses more time but reuses workspace across recursive sub-problems, keeping total space to O(log² n) via divide-and-conquer reachability
CThe simulation converts space usage to randomness, reducing worst-case space from log² n to log n with high probability
DThe simulation encodes the nondeterministic branch choices in the work tape, using log n bits per level of branching
Savitch's proof works by asking: is t reachable from s in ≤ k steps? To answer this, guess a midpoint m and recursively check s→m in k/2 steps AND m→t in k/2 steps. This recursion has log n levels (halving k each time), and each level requires log n bits for the midpoint and counter. Total space: O(log² n). The key insight is that space can be reused: once the s→m sub-check is done, that workspace is cleared before checking m→t. Time cannot be reused the same way — if you've already spent time on a branch that failed, you can't get it back. This asymmetry explains why NL ⊆ SPACE(log² n) but we don't know NL ⊆ TIME(n^c) for small c.
Question 3 True / False
An NL machine can solve the graph reachability problem on an n-node graph while storing only the current node index and a step counter, because both require only O(log n) bits.
TTrue
FFalse
Answer: True
True. A graph with n nodes can be indexed with ⌈log₂ n⌉ bits — enough to name any node. A step counter bounded by n (since any simple path has at most n − 1 edges) also requires O(log n) bits. Together these constitute the entire working memory needed: store the current node, check that an edge exists to a guessed next node (readable from the input tape), update the counter, overwrite the current node. Total workspace: O(log n). This is the canonical demonstration of how nondeterministic log-space captures graph reachability — a problem central to algorithm design — by leveraging the ability to 'forget' the path history while guessing it forward.
Question 4 True / False
Since NL ⊆ P by Savitch's theorem, most problem in NL can be efficiently solved in practice using the deterministic algorithm implied by the proof.
TTrue
FFalse
Answer: False
False. Savitch's theorem shows NL ⊆ SPACE(log² n) ⊆ P (since SPACE(log² n) ⊆ P by the time-space tradeoff), but the resulting deterministic algorithm's time complexity may be polynomial with a large exponent or constant. 'Contained in P' means polynomial time exists in principle, not that the algorithm is efficient in practice. Moreover, the proof constructs a simulation that works in log² n space but may use time exponential in log n for each space-bounded step. Separately, complexity containment tells you the class boundary, not whether we have good algorithms for specific problems — NL problems like graph reachability happen to have very fast practical algorithms, but Savitch's theorem is not why.
Question 5 Short Answer
What is the key insight behind Savitch's proof that NL ⊆ SPACE(log² n)? Specifically, why can the deterministic simulation avoid storing all nondeterministic branches simultaneously?
Think about your answer, then reveal below.
Model answer: Savitch's proof uses a divide-and-conquer reachability approach: to check if t is reachable from s in k steps, enumerate all possible midpoints m and recursively verify s→m in k/2 steps and m→t in k/2 steps. The space saving comes from sequential reuse: the s→m sub-check occupies log n bits on the work tape, and once it finishes (success or failure), that space is completely freed before the m→t sub-check begins. The recursion has depth log n (since k is halved each level), and each level uses log n bits, giving O(log² n) total. This works because space, unlike time, is reusable across branches. A nondeterministic machine explores all branches in parallel; Savitch's simulation explores them sequentially, clearing and reusing workspace between branches at the cost of more time.
This contrast between space and time reuse is a fundamental insight in complexity theory. Time spent on a failed branch is genuinely lost; space occupied during a failed branch can be reclaimed and reassigned. This asymmetry partially explains why L ⊆ NL has a much tighter bound (at most quadratic space blowup for determinism vs. nondeterminism) than P ⊆ NP (where the deterministic simulation of polynomial-time nondeterminism might require exponential time). It also motivates why researchers study space complexity separately from time complexity — the two resources behave fundamentally differently.