<p>In the course of trying to give a more natural answer to a <a href="https://cstheory.stackexchange.com/questions/40212/are-space-and-time-hierarchies-even-comparable/">previous question of mine</a> involving the complexity classes <span class="math-container">$$SUBLOG=\{L\mid L \text{ is recognizable by a sublogarithmic-space TM} \}$$</span> and <span class="math-container">$DTIME(n)$</span> I need a language in <span class="math-container">$SUBLOG$</span> that is not in <span class="math-container">$DTIME(n)$</span> (I already know the other direction).</p>
<p>However, I'm not very familiar with sublogarithmic space and <a href="http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&amp;arnumber=315816" rel="nofollow noreferrer">Liskiewicz and Reischuk's paper</a> 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?</p>

CC BY-SA 4.0
2020-08-29T06:11:39.010Z
Is this DTIME(n) on multi-tape Turing machines, or single-tape?
Emil Jeřábek
CC BY-SA 4.0
2020-09-02T12:11:01.897Z
@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?
Neal Young
CC BY-SA 4.0
2020-09-03T12:11:38.443Z
@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).
Kristoffer Arnsfelt Hansen
<time-complexity><space-complexity>
Is $SUBLOG\subset DTIME(n)$?
exfret
# Is $SUBLOG\subset DTIME(n)$?

(Asked by: username_0 on 2018-03-17)

In the course of trying to give a more natural answer to a [previous question of mine](https://cstheory.stackexchange.com/questions/40212/are-space-and-time-hierarchies-even-comparable/) 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](http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=315816) 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?

**Tags:** time-complexity, space-complexity
> **Comments:**
> **username_1**: Is this DTIME(n) on multi-tape Turing machines, or single-tape?  
> **username_2**: @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?  
> **username_3**: @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).  

---

## 0 answers

