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.

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?

share|improve this question
AFAIR, the result only holds for space constructable bounds, not for arbitrary $f(n)\geq\log n$. –  Kaveh Feb 10 '13 at 6:58

1 Answer 1

up vote 8 down vote accepted

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.

share|improve this answer

Your Answer


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.