P44 · Inductive counting

🔊 Listen

1 · The Immerman–Szelepcsényi theorem · NL = coNL

Immerman 1988 and Szelepcsényi 1987 independently proved: NL = coNL. Equivalently, ¬PATH (UNREACHABILITY) is in NL. This is a surprising and deep result — nondeterministic log space is closed under complement, while nondeterministic polynomial time (NP vs coNP) is open.

Inductive counting · the technique

For each i, let c_i = |{v : v is reachable from s in ≤ i steps}|. Compute c₀, c₁, …, c_n inductively in nondeterministic log space.

Key recurrence: c_i+1 = (number of vertices v such that either v is in the reach-set at step i, or v has a predecessor in the reach-set at step i). Both checks use the value c_i as a witness count — the nondeterministic machine guesses which c_i vertices are in the reach-set, verifies each, and counts those satisfying the property.

Using c_n to decide UNREACHABILITY

Given c_n = number of vertices reachable from s. To certify that t is unreachable: nondeterministically guess c_n reachable vertices v₁, …, v_{c_n}, each different from t, and verify each is reachable (using the PATH algorithm). If all c_n are accounted for and t isn't among them, t must be unreachable.

Space used at each step: counters of size O(log n), one current vertex of size O(log n). All operations fit in log space. The whole construction takes nondeterministic log space.

🔊 Listen

2 · Animated demo · auto-plays · loops

🔊 Listen

3 · Pitfalls

The counts c_i are exact, not bounded. The whole technique depends on c_i being precisely the number of reachable-by-i-steps vertices. Approximation breaks the witness logic.
"Inductive counting" doesn't mean we store the reach-set. We only store c_i. The actual reach-set has too many vertices to enumerate explicitly. Nondeterminism lets us re-verify on the fly.
NL = coNL is for log space, not polynomial time. The proof technique relies on configurations being log-size. It doesn't extend to NP — there's no analogous inductive counting for NP-witnesses.

🔊 Listen

4 · Q&A defence notes

Q1. Why does counting help?
Once we know c_n, we can verify "v is unreachable" by nondeterministically witnessing all c_n reachable vertices (each different from v) and verifying each is reachable. If we account for all c_n and v isn't among them, v must be unreachable.
Q2. Why does this work for NL but not for NP?
In NL, configurations are polynomial in number (poly(n)) and log-size, so counting them and re-verifying each fits in log space. In NP, the witness space is exponential and the time budget is poly — there's no way to count witnesses inductively in poly time.
Q3. What does NL = coNL really mean?
PATH ∈ NL means "is there a path?" can be verified by a nondeterministic log-space machine. NL = coNL means UNREACHABILITY ∈ NL — "is there NO path?" can also be verified that way. NL is "self-dual" under complement, unlike NP (where NP = coNP is conjectured false).
Q4. What other classes are closed under complement?
P (deterministic class). NSPACE(f) for any f ≥ log n. coNL itself. But NP and coNP appear distinct, although unproven. The difference seems related to the time/space asymmetry — space is reusable, time isn't.

🔊 Listen

5 · Where to read more

Sipser: Theorem 8.27 (Immerman–Szelepcsényi). Lecture notes: Module 7 slide 4. Companion problems: P42 (PATH ∈ NL), P43 (PATH NL-complete).