I'm trying to decide which of the following statements are true:

  1. $\mathsf{NSpace}(\log \log n) = \mathsf{coNSpace}(\log \log n )$

  2. $\mathsf{NSpace}(\lg^2n) = \mathsf{coNSpace}(\lg^2n)$

  3. $\mathsf{NSpace}(\sqrt n) = \mathsf{coNSpace}(\sqrt n)$

I thought immediately that (1) is correct since $\lg \lg n < \lg n$, and since $\mathsf{NL} = \mathsf{coNL}$, I thought that the statement yields from it. I thought that since we don't know if $\mathsf{P} = \mathsf{PSPACE}$, we can't say anything about a class which is bigger than $\lg n$ and a subset of $P$.

But it is exactly the opposite. (1) is not necessarily true while (2) and (3) are necessarily true. Why is that?

The question is from a past midterm that I'm solving now.

  • $\begingroup$ For (1): Try to show that $\{a^nb^n \mid n\in \mathbf{N}\}$ is not in ${\sf NSPACE}(\log\log n)$ but it is in ${\sf coNSpace}(\log\log n)$. Both statements are not trivial. $\endgroup$
    – A.Schulz
    Dec 14, 2012 at 9:42

1 Answer 1


I can't think of any counter-example for (i) right now. But (ii) and (iii) are true due to the Immerman–Szelepcsényi theorem[1], according to which $\text{NSPACE}(s(n)) = \text{co-NSPACE}(s(n))$ for all $s(n) \geq \log(n)$.

[1]: Wikipedia - Immerman–Szelepcsényi theorem


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.