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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.