World's most popular travel blog for travel bloggers.

[Solved]: Does $\mathsf{NSPACE}( f (n)) = \mathsf{coNSPACE}( f (n))$ hold for $ f(n) < \log (n) $?

, , No Comments
Problem Detail: 

It's known that for $f(n) \geq \log n$, $\mathsf{NSPACE}(f(n)) = \mathsf{coNSPACE}(f(n))$.

What if $f(n)<\log n$? Are they also equal?

Asked By : URL87

Answered By : Reza

Immerman–Szelepcsényi theorem works under logarithmic reductions. Sublogarithmic space classes have different reductions. The TMs working within sublogarithmic space cannot even record the the length of the input. It has been shown that the space hierarchy for any sublogarithmic bound in Ω(log log n)-- o(log n) is infinite. You can find it in following references:

V. Geffert. Sublogarithmic σ2-space is not closed under complement and other separation results. Theoretical Informatics and Applications, 27:349–366, 1993.

M. Liśkiewicz and R. Reischuk. Separating the lower levels of the sublogarithmic space hierarchy. In Proceedings of the Symposium on Theoretical Aspects of Computer Science, pages 6–27, 1993.

B. von Braunmuhl "Alternation for two-way machines with sublogarithmic space". In Proceedings of the Symposium on Theoretical Aspects of Computer Science, pages 5–15, 1993.

The paper The complexity world below logarithmic space by M. Liśkiewicz and R. Reischuk contains an excellent wrap up of the sublogarithmic space.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9625

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback