 Inductive counting

Inductive counting certifies complete reachable sets while retaining only a count and a few vertex indices. For a directed graph with $N$ vertices and start $s$, let $R_k$ contain the vertices reachable in at most $k$ steps and write $r_k=|R_k|$.

Suppose the exact count $r_k$ is known. A nondeterministic computation can enumerate each vertex, guess which belong to $R_k$, and justify every positive guess by a path of length at most $k$. Requiring exactly $r_k$ justified vertices prevents omissions: false positives have no valid path certificate. To certify $v\notin R_{k+1}$, also check $v\ne s$ and that none of those enumerated vertices has an edge to $v$.

Starting from $r_0=1$, certify membership or nonmembership for each vertex and accumulate $r_{k+1}$. After $N-1$ stages every reachable vertex has been counted, since cycles can be removed from a reaching path. Loop counters and the current vertex use only logarithmic space; guessed paths are checked one edge at a time, and the full reachable set is never stored. This is the counting mechanism behind the Immerman–Szelepcsényi theorem.^[ref]