In the course of trying to give a more natural answer to a previous question of mine involving the complexity classes $SUBLOG=\{L\mid L \text{ is recognizable by a sublogarithmic-space TM} \}$ and $DTIME(n)$ I need a language in $SUBLOG$ that is not in $DTIME(n)$ (I already know the other direction).

However, I'm not very familiar with sublogarithmic space and Liskiewicz and Reischuk's paper overviewing the topic deals more with alternating machines than it does with deterministic ones, which I was more interested in. Is it known whether there is a sublogarithmic language requiring super-linear space?


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.