Neil Immerman proved closure of 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, . His paper's proof uses inductive counting of reachable configurations.[ref]
Nondeterministic Space is Closed Under Complementation by Neil Immerman. Theorem1 and Lemmas1–2
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 bound. This makes complementation possible without storing every reached configuration at once. The result concerns nondeterministic space, and does not establish the analogous equality for polynomial time.
Articles by others on the same topic
Neil Immerman is a prominent computer scientist and mathematician known for his contributions to computational complexity theory and formal language theory. He is best known for his work on the expressiveness and complexity of various computational models, particularly in the context of logics and automata. One of Immerman's key contributions is the development of the concept of "definability" in computational complexity, which relates to how certain properties and functions can be expressed in logical languages.