- From Savitch's theorem we have $NL^2 \subseteq L^4$, which is deterministic and thus closed under complement.
- From Immerman–Szelepcsényi theorem we have $NL = coNL$.
Why then $NL^2 = coNL^2$
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityWhy then $NL^2 = coNL^2$
The Immerman–Szelepcsényi theorem states that $\mathsf{NSPACE}(s(n))$ is closed under complementation whenever $s(n) \geq \log n$.