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 time?

  • 2
    $\begingroup$ Is this DTIME(n) on multi-tape Turing machines, or single-tape? $\endgroup$ Aug 29, 2020 at 6:11
  • 2
    $\begingroup$ @EmilJeřábek, OP must have in mind that DTIME(n) is defined using a multi-tape TM, because the language of any single-tape TM that runs in time $o(n\log n)$ is regular, so would be in SUBLOG (and OP says he knows a language in DTIME$(n)$ that is not in SUBLOG). Just out of curiosity, Exfret, can you describe the language you know that is in DTIME$(n)$ but not SUBLOG, and can somebody give an example of a language that is in SUBLOG but not regular? $\endgroup$
    – Neal Young
    Sep 2, 2020 at 12:11
  • 3
    $\begingroup$ @NealYoung PALINDROMES comes to mind as a language in $\mathrm{DTIME}(n)$ not in in $\mathrm{DSPACE}(o(\log n))$. The language $\mathrm{BIN} = \{\mathrm{bin}(1)\#\mathrm{bin}(2)\#\mathrm{bin}(3)\#\cdots\#\mathrm{bin}(m) \mid m \geq 1\}$ is a non-regular language in $\mathrm{DSPACE}(\log \log n)$. (I will not argue for the space bound as I use it as an exercise). $\endgroup$ Sep 3, 2020 at 12:11


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.