3
$\begingroup$

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.

$\endgroup$
  • $\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 '12 at 9:42
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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