Place Directed Reachability in NL

Give a log-space nondeterministic reachability algorithm with a bounded path-length counter.

Problem

For a directed graph $G$ with vertices numbered $1,\ldots,n$ and distinguished $s,t$, give a nondeterministic $O(\log n)$-space decider for whether $t$ is reachable from $s$. Ensure all branches halt and account for adjacency access, vertex storage, and the step counter.

Prerequisites

Know the unit definitions and how resources are measured against encoded input length. Distinguish a conditional theorem, a reduction, and an algorithm.

Hint 1

If a path exists, a simple path of at most $n-1$ edges exists.

Hint 2

Store only the current vertex, not the path.

Hint 3

At each step guess the next vertex and verify its edge by scanning the read-only input.

Full solution

Store a current-vertex register $v$, initialized to $s$, and a counter $i=0$. If $v=t$, accept. While $i<n-1$, nondeterministically choose a number $u\in\{1,\ldots,n\}$. Scan the read-only encoding of $G$ to verify that $(v,u)\in E$; if not, reject this branch. Otherwise set $v:=u$, increment $i$, and test again for $t$. Reject when the budget is exhausted.

Each register for a vertex needs $\lceil\log n\rceil$ bits, as does the counter. A constant number of input-head positions and flags also requires $O(\log n)$ bits under the standard read-only input/work-tape convention. For an adjacency matrix, the machine computes or scans to the relevant entry using logarithmic counters. For an adjacency-list encoding, it scans for the pair while retaining $v,u$. Repeated scans affect time but not work space. Thus the total work space is $O(\log n)$.

Every branch makes at most $n-1$ successful edge guesses and each verification scan halts, so this is a decider rather than a semidecider. If $t$ is reachable from $s$, remove cycles from a shortest walk to obtain a simple directed path with at most $n-1$ edges. One branch guesses exactly its vertices and accepts. If $t$ is not reachable, every sequence of verified edges remains a walk from $s$ and can never reach $t$, so every branch rejects. Hence $\mathrm{STCON}\in\mathrm{NL}$.

The algorithm may use polynomial time: there are only $n$ iterations, each with a polynomial input scan. Nondeterminism changes the acceptance semantics, not the space charged per branch; we do not store or explore all branches simultaneously.

The counter is essential for guaranteed halting because blindly guessing a walk could cycle forever. Storing a visited set would also prevent cycles but costs $\Theta(n)$ bits and would miss the desired log-space bound. The simple-path lemma supplies boundedness without that storage.

Checkpoints

Check both logical directions, halting of every relevant branch, and that output length and construction time are polynomial in the encoded input length.

Common mistakes

• Storing the whole guessed path or a visited bit vector.
• Omitting the counter and obtaining a non-halting branch.
• Charging space for all nondeterministic branches at once.

Sources and verification

• Merged summary, pp. 114-117
• Sipser 3e, sec. 8.4
• Arora-Barak draft, sec. 4.3
• Catalog mapping: data/exercises.json; statements and solutions are independently written; personal submissions are non-authoritative.

Provenance and confidence

The exercise is an original synthesis. Confidence reflects verification of the mathematical claim against the textbook sources listed above; course sources are used only where direct coverage is identified.