= Neil Immerman
{c}
<Neil Immerman> proved closure of <space complexity>[nondeterministic space] under complementation for space bounds at least logarithmic, independently of the result associated with the other name in the <Immerman–Szelepcsényi theorem>. In particular, $\mathrm{NL}=\mathrm{coNL}$. His paper's proof uses <inductive counting> of reachable configurations.<Nondeterministic Space is Closed Under Complementation by Neil Immerman>[Theorem1 and Lemmas1–2]{ref}
The obstacle is that guessing a path certifies reachability, while failure of one guessed path does not certify nonreachability. Counting the complete reachable set and verifying its enumeration supplies the missing certificate within a small <space complexity>[space bound]. This makes complementation possible without storing every reached configuration at once. The result concerns <space complexity>[nondeterministic space], and does not establish the analogous equality $\mathrm{NP}=\mathrm{coNP}$ for <polynomial time>.
Back to article page
