Problem Detail: 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.
Asked By : Jozef
Answered By : Martin Jonáš
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
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7385 Ask a Question Download Related Notes/Documents
