P42 · NL PATH

🔊 Listen

1 · PATH ∈ NL · the canonical nondeterministic log-space algorithm

PATH = {⟨G, s, t⟩ : directed graph G has a path from s to t}. PATH is the canonical NL problem and arguably the defining example of nondeterministic log-space — it's NL-complete (Problem 43) and one of the cleanest "nondeterminism actually helps" demonstrations.

The nondeterministic algorithm

v ← s; counter ← 0
while counter ≤ |V|:
   if v = t: accept
   v ← nondet. choice from neighbours of v
   counter ← counter + 1
reject

Memory: v fits in ⌈log₂ n⌉ bits, counter fits in ⌈log₂(n+1)⌉ bits, plus O(1) state. Total: O(log n) work-tape space.

The algorithm wins because nondeterminism lets it guess the right next vertex at each step. Acceptance is existential: PATH accepts if any guessing sequence reaches t.

Why deterministic LOGSPACE can't do PATH (probably)

A deterministic algorithm would need to remember which neighbours it has tried. With only O(log n) bits, it can't store a non-trivial set of visited vertices. PATH ∈ L is open (whether L = NL). DFS uses too much stack for log space.

NL is closed under reductions; therefore the existence of a log-space reduction to PATH proves a problem is in NL.

🔊 Listen

2 · Animated demo · auto-plays · loops

🔊 Listen

3 · Pitfalls

NL acceptance is existential. Accept iff some branch finds t. The other branches' failures don't matter.
The counter prevents infinite loops. Without it, the nondeterministic walk could move randomly forever. With ≤ |V| steps, we trip the cap if no t is found.
NL ⊆ P. Any nondeterministic log-space machine has at most poly(n) configurations; reachability among them is in P (BFS). So NL ⊆ P. Whether NL = P is open.

🔊 Listen

4 · Q&A defence notes

Q1. Why nondeterministic and not deterministic?
A deterministic log-space machine doesn't have enough memory to remember which neighbours have been tried (would need Ω(|V|) bits to store the visited set). Nondeterminism lets us "magically" guess the right neighbour at each step.
Q2. Why must counter ≤ |V|?
If a path exists, it has length ≤ |V| − 1 (no need to repeat vertices). Capping at |V| ensures termination — without the cap, a nondeterministic walk could revisit vertices and loop forever.
Q3. Is PATH in L?
Open. Showing PATH ∈ L is equivalent to L = NL — a major open question. Reingold (2008) showed UNDIRECTED-PATH ∈ L, but the directed version remains open.
Q4. What's coNL?
coNL = complements of NL languages = "for every nondeterministic branch, the answer is no." Immerman–Szelepcsényi (1987): coNL = NL. So nondeterministic space classes are closed under complement, unlike NP (which is open).

🔊 Listen

5 · Where to read more

Sipser: §8.4, Example 8.21 (PATH algorithm). Lecture notes: Module 7 slide 2. Companion problems: P41 (log space), P43 (PATH NL-complete), P44 (inductive counting / coNL = NL).