Nondeterministic Space is Closed Under Complementation by Neil Immerman
= Nondeterministic Space is Closed Under Complementation by Neil Immerman
{c}
{tag=Work by Neil Immerman}
{title2=1988}
{title2=10.1137/0217058}
By <Neil Immerman>. SIAM Journal on Computing 17(5), 935–938, 1988.
Author-hosted primary paper: https://people.cs.umass.edu/~immerman/pub/space.pdf
Theorem 1 and Lemmas 1–2 establish complement closure by counting reachable configurations and verifying complete reachable-set enumeration.