patternMinor
Equality of NSpace and coNSpace classes
Viewed 0 times
equalityconspaceandclassesnspace
Problem
I'm trying to decide which of the following statements are true:
-
$\mathsf{NSpace}(\log \log n) = \mathsf{coNSpace}(\log \log n )$
-
$\mathsf{NSpace}(\lg^2n) = \mathsf{coNSpace}(\lg^2n)$
-
$\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.
-
$\mathsf{NSpace}(\log \log n) = \mathsf{coNSpace}(\log \log n )$
-
$\mathsf{NSpace}(\lg^2n) = \mathsf{coNSpace}(\lg^2n)$
-
$\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.
Solution
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
[1]: Wikipedia - Immerman–Szelepcsényi theorem
Context
StackExchange Computer Science Q#7385, answer score: 5
Revisions (0)
No revisions yet.