Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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. – A.Schulz Dec 14 '12 at 9:42
up vote 4 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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