Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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|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
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.