P43 · PATH NL-complete

🔊 Listen

1 · PATH is NL-complete · the configuration-graph reduction

Sipser Theorem 8.25: PATH is NL-complete under log-space reductions. We show NL-hardness by reducing every NL machine's acceptance question to PATH.

The configuration graph G_M,w

For an NL machine M on input w, build a directed graph whose vertices are M's configurations on w (state, head positions, work-tape contents). Add an edge C → C' iff C' follows C by one application of M's transition relation.

M accepts w ⇔ there is a directed path in G_M,w from the start configuration to an accepting configuration. That's exactly PATH.

Why poly(n) vertices

A configuration consists of: state (constant), input head position (O(log n) bits), work-tape head position (O(log n)), work-tape contents (O(log n)). Total: O(log n) bits per configuration. So at most 2^{O(log n)} = poly(n) distinct configurations.

Why the reduction itself uses only log space

The reduction outputs the graph (V, E). It doesn't store G_M,w in memory — it generates vertices and edges on demand. Given a configuration C (O(log n) bits to write), iterate possible next configurations and check whether each follows by a δ-step. Each check is O(log n) space. Total reduction: log-space.

Combining: every NL problem reduces to PATH via a log-space many-one reduction; PATH ∈ NL; therefore PATH is NL-complete. Any other NL problem becomes NL-complete iff it has a similar log-space reduction from PATH.

🔊 Listen

2 · Animated demo · auto-plays · loops

🔊 Listen

3 · Pitfalls

Reductions for NL use log-space, not polynomial-time. NL-completeness is defined under ≤_L, not ≤_p. A polynomial-time reduction is too coarse — it could output exponentially many configurations.
Configurations are short. O(log n) bits, not poly. That's why 2^{O(log n)} = poly(n) configurations exist.
Don't materialise the graph. The log-space reduction computes adjacencies on demand. Materialising the whole graph would take poly(n) space — too much for log space.

🔊 Listen

4 · Q&A defence notes

Q1. Why poly(n) configurations?
A configuration consists of: state (constant), two head positions (O(log n) bits each), and work-tape contents (O(log n)). Total O(log n) bits per configuration. 2^{O(log n)} = poly(n) distinct configurations.
Q2. Why is the reduction in log space?
We don't materialise the whole graph. Given a configuration C (a short string), we compute its successors by simulating M's transition function for one step. Each computation uses O(log n) space and produces O(log n)-size output configurations.
Q3. So NL = {L : L log-space reduces to PATH}?
Yes. PATH being NL-complete under log-space reductions means: NL is precisely the set of languages log-space reducible to PATH. This characterisation is the standard way to prove NL membership.
Q4. Is the reduction direction NL → PATH or PATH → NL?
NL-hardness goes from any NL problem TO PATH (every NL problem reduces to PATH). NL membership of PATH is shown directly (Problem 42). Together: PATH is NL-complete.

🔊 Listen

5 · Where to read more

Sipser: Theorem 8.25 (PATH is NL-complete). Lecture notes: Module 7 slide 3. Companion problems: P42 (PATH in NL), P44 (NL = coNL), P41 (log space).