<p>If $DTIME(f(n))$ is defined as the class of all languages decidable in $O(f(n))$ time by a two tape Turing machine, then I suspect that the answer is no.  In other words, I think that there does not always exist a strictly intermediate time complexity class.</p>

<p><strong>Note:</strong> This answer might not be exactly what you are looking for because I'm considering non-computable functions and I don't include every detail of the argument.  But, I felt that it is a good start.  Please feel free to ask any questions.  Maybe I can fill in these details further at some point or maybe this will lead to a better answer from an interested reader.</p>

<p>Consider functions of the form $f : \mathbb{N} \rightarrow \mathbb{N}$.  We refer to these functions as natural number functions.</p>

<blockquote>
  <p><strong>Claim 1:</strong> I claim that we can construct a very slow growing non-decreasing natural number (non-computable) function
  $\varepsilon(n)$ such that:</p>
  
  <p>(1) $\varepsilon(n)$ is non-decreasing</p>
  
  <p>(2) $\varepsilon(n) = \omega(1)$</p>
  
  <p>(3) For all unbounded computable $f: \mathbb{N} \rightarrow \mathbb{N}$, the set
  $\{ n \; \vert \; \varepsilon(n) \leq f(n) \}$ is infinite.</p>
</blockquote>

<p>We construct $\varepsilon(n)$ as a slow growing non-decreasing step function. Let us enumerate all unbounded computable functions $\{ f_i \}_{i \in \mathbb{N}}$. We want to construct $\varepsilon(n)$ in such a way that for every $i$ and every $j \leq i$, $min\{ k \; \vert \; \varepsilon(k) \geq i\} \geq min\{ k \; \vert \; f_{j}(k) \geq i \}$. In other words, we wait to map $\varepsilon(n)$ to $i$ until the first $i$ functions in the enumeration have mapped to a value greater than or equal to $i$ at least once.  Then, $\varepsilon(n)$ continues to map to $i$ until the first $i+1$ functions in the enumeration have mapped to a value greater than or equal to $i+1$ at least once and at this point it starts mapping to $i+1$. If we continue this iterative process for constructing $\varepsilon(n)$, then for any given unbounded computable function, although $\varepsilon(n)$ might not always be smaller, it will infinitely often be at least as small.</p>

<p><strong>Note:</strong> I just provided some intuition behind claim 1, I did not provide a detailed proof.  Please feel free to join in on discussion below.</p>

<p>Because $\varepsilon(n)$ is such a slow growing function, we have the following:</p>

<blockquote>
  <p><strong>Claim 2:</strong> For all computable natural number functions $f(n)$ and $h(n)$, if $h(n) = \Omega(\frac{f(n)}{\varepsilon(n)})$ and $h(n) = O(f(n))$, then $h(n) = \Theta(f(n))$.</p>
</blockquote>

<p>For claim 2, if there existed a computable function $h(n)$ between $\frac{f(n)}{\varepsilon(n)}$ and $f(n)$ such that $h(n) \neq \Theta(f(n))$, then we would be able to compute an unbounded natural number function that grows more slowely than $\varepsilon(n)$ which isn't possible.  </p>

<p>Let me explain some relevant details.  Suppose for sake of contradiction that such a function $h(n)$ existed.  Then, $\lfloor \frac{f(n)}{h(n)} \rfloor$ is unbounded.</p>

<p><strong>Note:</strong> The preceding function is computable because $f(n)$ and $h(n)$ are computable.</p>

<p>Since $h(n) = \Omega(\frac{f(n)}{\varepsilon(n)})$, we have $\lfloor \frac{f(n)}{h(n)} \rfloor = O(\varepsilon(n))$.  It follows that there is some constant $\alpha$ such that for all $n$ sufficiently large, $\lfloor \alpha \frac{f(n)}{h(n)} \rfloor &lt; \varepsilon(n)$.  Since this function is unbounded and computable we may apply Claim 1 to get that $\varepsilon(n) \leq \lfloor \alpha \frac{f(n)}{h(n)} \rfloor$ infinitely often which contradicts the previous statement.</p>

<blockquote>
  <p><strong>Claim 3:</strong> For a time constructible function $f(n)$, we have that $DTIME(\frac{f(n)}{\varepsilon(n)}) \subsetneq DTIME(f(n))$, yet there does <strong>not</strong> exist $h(n)$ such that $\frac{f(n)}{\varepsilon(n)} \leq h(n) \leq f(n)$ and $DTIME(\frac{f(n)}{\varepsilon(n)}) \subsetneq DTIME(h(n)) \subsetneq DTIME(f(n))$.</p>
</blockquote>

<p>In order to just show that, $DTIME(\frac{f(n)}{\varepsilon(n)}) \subsetneq DTIME(f(n))$ we need to use a stronger time hierarchy theorem and this is where we use the assumption that the number of tapes is fixed (we said two tapes above).  See "The tight deterministic time hierarchy" by Martin Furer.</p>

<p>Since there are no computable natural number functions between $\frac{f(n)}{\varepsilon(n)}$ and $f(n)$ other than those that are $\Theta(f(n))$, we have that for every function $h(n)$ such that $\frac{f(n)}{\varepsilon(n)} \leq h(n) \leq f(n)$ and $h(n) \neq \Theta(f(n))$, $DTIME(\frac{f(n)}{\varepsilon(n)}) = DTIME(h(n))$.</p>

CC BY-SA 3.0
2017-02-28T10:08:20.347Z
Yes, this is exactly what I had in mind too, but then got confused somewhere along the way. I just want to note, that $\epsilon(n)$ needn't be small at all; a similar argument shows that the lower function $\frac{f(n)}{\epsilon(n)}$ can be replaced with a function that is always either $f(n)$ or $0$, and the upper function $f(n)\epsilon(n)$ can be replaced with a function that is always either $f(n)$ or $\infty$.
domotorp
CC BY-SA 3.0
2017-02-28T15:11:26.253Z
@RickyDemer Yes, you are right!  Thank you very much for catching that.  I edited my answer to add the word unbounded.  :)
Michael Wehar
CC BY-SA 3.0
2017-02-28T15:15:00.370Z
@domotorp Thank you very much for the comment!  Yes, I believe your right!  Neat!  :)
Michael Wehar
CC BY-SA 3.0
2017-03-01T02:50:44.070Z
Im not entirely convinced about Claim 1. Consider $f_i(n) = 1$ if $n \leq i$, $n-i$ otherwise. Considering this enumeration, is $\epsilon(n) = \Theta(1)$?
S. Pek
CC BY-SA 3.0
2017-03-03T07:12:39.900Z
@S.Pek Thank you for your question!  Yes, my previous construction wasn't so clear so I made some edits to my answer and hopefully it's a little more clear.
Michael Wehar
CC BY-SA 3.0
2017-03-03T07:14:16.447Z
Basically $\varepsilon(n)$ will wait to grow until the first $i$ functions grow a little bit (that is surpass $i$).  Then, $\varepsilon(n)$ will sprout up 1 step.  Then, it waits to grow until the first $i+1$ functions have all grown a little bit and so on.
Michael Wehar
CC BY-SA 3.0
2017-03-03T07:17:44.153Z
With your example, it seems that roughly for $n$ from 1 to $2 * i$, $\varepsilon(n)$ may be great than $f_i(n)$ and then for larger values of $n$, it will always be less.
Michael Wehar
CC BY-SA 3.0
2017-03-03T15:51:32.717Z
I have two more concerns of this proof:

1) In claim 2 you said that the contradiction arises from the fact that there cannot exist a computable $\epsilon(n)$ as it equals $|h(n)-f(n)|$. I believe this to be a typographical error, as it should say there exist a $k'$ such that $\epsilon(n) = |h(n) - k'\cdot f(n)|$. But note that $k'$ need not be computable, so the argument need not hold.

2) You used the result by Furer in Claim 3. However, the result only holds for time-constructable functions, but $\frac{f(n)}{\epsilon(n)}$ need not be time-constructable.
S. Pek
CC BY-SA 3.0
2017-03-04T22:52:30.243Z
@S.Pek Thank you!  I really appreciate your follow-up comments!  Yes, I will make some corrections with the above informal explanation for claim 2.  However, I believe that claim 3 is justified by Furer's result because if $f(n)$ is time constructible, then $DTIME(\frac{f(n)}{\varepsilon(n)}) \subseteq DTIME(o(f(n))) \subsetneq DTIME(f(n))$.
Michael Wehar
CC BY-SA 3.0
2017-03-05T05:55:47.690Z
@S.Pek A correction to the previous comment, I meant to say since $\frac{f(n)}{\varepsilon(n)} = o(f(n))$, by Furer's work, we have that $DTIME(\frac{f(n)}{\varepsilon(n)}) \subsetneq DTIME(f(n))$.
Michael Wehar
CC BY-SA 3.0
2017-03-05T06:36:16.313Z
I believe Furer's claim is that if $f,g$ time-constructable and $f(n) = o(g(n))$, then $DTIME(f(n)) \subsetneq DTIME(g(n))$. You seem to be implying something stronger, namely that it holds when $f,g$ are not time-constructable. This cannot be true, as it would violate Borodin's Gap Theorem.
S. Pek
CC BY-SA 3.0
2017-03-05T08:19:39.873Z
@S.Pek Please correct me if I'm wrong, but I believe that it is still true if $g(n)$ is time-constructible.  (I do make the time-constructibility assumption in claim 3.  In other words, I assume that one side is time-constructible.)
Michael Wehar
CC BY-SA 3.0
2017-03-05T08:37:17.300Z
The argument from Furer's paper seems to validate this claim that we only require that the larger of the two functions be time-constructible.  Please let me know if you find something wrong with this claim.
Michael Wehar
CC BY-SA 3.0
2017-03-07T06:43:37.697Z
@S.Pek Hi again!  I revised the answer a bit.  I believe that claim 2 and claim 3 are up to par now.  I didn't write a formal proof, but I believe I included enough detail to be convincing.  Thanks again and please let me know if you have any comments, suggestions, concerns, or questions.  Thank you!  :)
Michael Wehar
CC BY-SA 3.0
2017-02-28T07:32:16.280Z
2017-03-07T06:45:10.973Z
2017-03-07T06:45:10.973Z
Michael Wehar
<p>If this result is true, it would strengthen the best-known deterministic time hierarchy theorem. [This is more of a comment than an answer, but too long for a comment. It leaves open the direct construction of a counterexample.] Recall that the best Deterministic Time Hierarchy Theorem we currently have is that if $f(n), g(n)$ are time-constructible, and $g(n) \leq o( f(n) / \log f(n) )$, then $\mathsf{DTIME}(g(n)) \subsetneq \mathsf{DTIME}(f(n))$. </p>

<p>Now suppose your desired result is true, and let $g(n)$ be a time-constructible function that is close to, but still little-oh of, $f(n) / \log(f(n))$, say, $g(n) = f(n) / (\log f(n))^{3/2}$. (This $g$ may not be time-constructible for arbitrary time-constructible $f$, but surely for many time-constructible $f$ this $g$ is also time-constructible.) Now, your desired result produces an $h$ such that $\mathsf{DTIME}(g(n)) \subsetneq \mathsf{DTIME}(h(n)) \subsetneq \mathsf{DTIME}(f(n))$. In order to avoid improving the current-best time hierarchy theorem, we would need both $g(n) = o( h(n) / \log(h(n)) )$ and $h(n) = o(f(n) / \log(f(n))$. These two together imply that $g(n) \leq o( f(n) / (\log(f(n)) \log(h(n)))$. Since $h(n) \geq g(n)$, we have $g(n) \leq o( \frac{f(n)}{\log(f(n)) \log(g(n))})$, or equivalently $g(n) \log g(n) \leq o(f(n) / \log(f(n)))$. But $g(n) \log(g(n)) = f(n) / (\log(f(n))^{3/2} [\log(f(n)) - (3/2) \log \log(f(n)] \sim f(n) / \sqrt{\log(f(n))}$, which is not $o(f(n) / \log(f(n))$.</p>

CC BY-SA 3.0
2017-02-28T08:02:01.777Z
Cool!  Also, note that there is a better time hierarchy theorem if the number of tapes is fixed.  See "The tight deterministic time hierarchy" by Martin Furer.
Michael Wehar
CC BY-SA 3.0
2017-02-28T08:27:56.663Z
@MichaelWehar: Thanks for the pointer! Indeed, when one gets so tight as to only require $g(n) = o(f(n))$, as Furer shows when the number of tapes is fixed, then my argument goes away. (And for basically the same reason, my argument goes away if this question were about space hierarchy instead of time: for space we have a perfectly tight hierarchy theorem even if # tapes isn't fixed.)
Joshua Grochow
CC BY-SA 3.0
2017-02-28T07:48:27.047Z
2017-02-28T07:48:27.047Z
Joshua Grochow
<p>I think such a behaviour is true for 1-Tape-DTMs. On the one hand, we have $\mathrm{DTIME}_1(O(n)) = \mathrm{DTIME}_1(o(n \log n))$. Unfortunately, the only reference I know is in German: R. Reischuk, Einführung in die Komplexitätstheorie, Teubner, 1990, Theorem 3.1.8.</p>

<p>On the other hand, it should be possible to separate $\mathrm{DTIME}_1(O(n))$ and $\mathrm{DTIME}_1(O(n \log n))$ by the language $\{ x \#^{2^{|x|}} x \mid x \in \{0,1\}^* \}$ using a standard crossing sequence argument.</p>

CC BY-SA 3.0
2017-03-06T07:16:16.633Z
2017-03-06T07:16:16.633Z
Markus Bläser
<p>A student of mine recently ask the following question: </p>

<p>Assume $$DTIME(f(n)) \subsetneq DTIME(g(n)).$$ Must there exist an $h(n)$ such that $$DTIME(f(n)) \subsetneq DTIME(h(n)) \subsetneq DTIME(g(n))?$$</p>

<p>This could probably be shown true by constructing an $h(n)$ if $f,g$ are time-constructible. But in general, I feel that this should be false similar to $DSPACE(o(\log(\log(n)))) = DSPACE(1)$.</p>

CC BY-SA 3.0
2017-02-27T15:10:07.103Z
Borodin's gap theorem mentioned here may be relevant: https://cstheory.stackexchange.com/questions/8583/non-constructible-functions-and-anomalous-results/8589#8589
Michael Wehar
CC BY-SA 3.0
2017-02-27T20:18:22.710Z
Do you allow $f(n),g(n)=O(1)$? Because then some example must exist for some functions that are zero everywhere, except the first place. Anyhow, doesn't this question make sense if $f\equiv g$ everywhere except one $n$?
domotorp
CC BY-SA 3.0
2017-02-28T02:55:02.953Z
Im sorry I dont quite follow the issue with $f(n),g(n) = O(1)$ as by definition $DTIME(f(n))=DTIME(g(n))$?
S. Pek
CC BY-SA 3.0
2017-02-28T06:34:53.597Z
Sorry about that, I misread the question and my earlier comment didn't make much sense.  I removed it.  Thank you.
Michael Wehar
<cc.complexity-theory>
Separating time classes
S. Pek
# Separating time classes

(Asked by: username_0 on 2017-02-27)

A student of mine recently ask the following question:

Assume $$DTIME(f(n)) \subsetneq DTIME(g(n)).$$ Must there exist an $h(n)$ such that $$DTIME(f(n)) \subsetneq DTIME(h(n)) \subsetneq DTIME(g(n))?$$

This could probably be shown true by constructing an $h(n)$ if $f,g$ are time-constructible. But in general, I feel that this should be false similar to $DSPACE(o(\log(\log(n)))) = DSPACE(1)$.

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: Borodin's gap theorem mentioned here may be relevant: https://cstheory.stackexchange.com/questions/8583/non-constructible-functions-and-anomalous-results/8589#8589  
> **username_2**: Do you allow $f(n),g(n)=O(1)$? Because then some example must exist for some functions that are zero everywhere, except the first place. Anyhow, doesn't this question make sense if $f\equiv g$ everywhere except one $n$?  
> **username_0**: Im sorry I dont quite follow the issue with $f(n),g(n) = O(1)$ as by definition $DTIME(f(n))=DTIME(g(n))$?  
> **username_1**: Sorry about that, I misread the question and my earlier comment didn't make much sense.  I removed it.  Thank you.  

---

## 3 answers

### Answer by username_1 on 2017-02-28. Score: 8 | Accepted answer

If $DTIME(f(n))$ is defined as the class of all languages decidable in $O(f(n))$ time by a two tape Turing machine, then I suspect that the answer is no. In other words, I think that there does not always exist a strictly intermediate time complexity class.

**Note:** This answer might not be exactly what you are looking for because I'm considering non-computable functions and I don't include every detail of the argument. But, I felt that it is a good start. Please feel free to ask any questions. Maybe I can fill in these details further at some point or maybe this will lead to a better answer from an interested reader.

Consider functions of the form $f : \mathbb{N} \rightarrow \mathbb{N}$. We refer to these functions as natural number functions.

> **Claim 1:** I claim that we can construct a very slow growing non-decreasing natural number (non-computable) function
> $\varepsilon(n)$ such that:
>
> (1) $\varepsilon(n)$ is non-decreasing
>
> (2) $\varepsilon(n) = \omega(1)$
>
> (3) For all unbounded computable $f: \mathbb{N} \rightarrow \mathbb{N}$, the set
> $\{ n \; \vert \; \varepsilon(n) \leq f(n) \}$ is infinite.

We construct $\varepsilon(n)$ as a slow growing non-decreasing step function. Let us enumerate all unbounded computable functions $\{ f\_i \}\_{i \in \mathbb{N}}$. We want to construct $\varepsilon(n)$ in such a way that for every $i$ and every $j \leq i$, $min\{ k \; \vert \; \varepsilon(k) \geq i\} \geq min\{ k \; \vert \; f\_{j}(k) \geq i \}$. In other words, we wait to map $\varepsilon(n)$ to $i$ until the first $i$ functions in the enumeration have mapped to a value greater than or equal to $i$ at least once. Then, $\varepsilon(n)$ continues to map to $i$ until the first $i+1$ functions in the enumeration have mapped to a value greater than or equal to $i+1$ at least once and at this point it starts mapping to $i+1$. If we continue this iterative process for constructing $\varepsilon(n)$, then for any given unbounded computable function, although $\varepsilon(n)$ might not always be smaller, it will infinitely often be at least as small.

**Note:** I just provided some intuition behind claim 1, I did not provide a detailed proof. Please feel free to join in on discussion below.

Because $\varepsilon(n)$ is such a slow growing function, we have the following:

> **Claim 2:** For all computable natural number functions $f(n)$ and $h(n)$, if $h(n) = \Omega(\frac{f(n)}{\varepsilon(n)})$ and $h(n) = O(f(n))$, then $h(n) = \Theta(f(n))$.

For claim 2, if there existed a computable function $h(n)$ between $\frac{f(n)}{\varepsilon(n)}$ and $f(n)$ such that $h(n) \neq \Theta(f(n))$, then we would be able to compute an unbounded natural number function that grows more slowely than $\varepsilon(n)$ which isn't possible.

Let me explain some relevant details. Suppose for sake of contradiction that such a function $h(n)$ existed. Then, $\lfloor \frac{f(n)}{h(n)} \rfloor$ is unbounded.

**Note:** The preceding function is computable because $f(n)$ and $h(n)$ are computable.

Since $h(n) = \Omega(\frac{f(n)}{\varepsilon(n)})$, we have $\lfloor \frac{f(n)}{h(n)} \rfloor = O(\varepsilon(n))$. It follows that there is some constant $\alpha$ such that for all $n$ sufficiently large, $\lfloor \alpha \frac{f(n)}{h(n)} \rfloor < \varepsilon(n)$. Since this function is unbounded and computable we may apply Claim 1 to get that $\varepsilon(n) \leq \lfloor \alpha \frac{f(n)}{h(n)} \rfloor$ infinitely often which contradicts the previous statement.

> **Claim 3:** For a time constructible function $f(n)$, we have that $DTIME(\frac{f(n)}{\varepsilon(n)}) \subsetneq DTIME(f(n))$, yet there does **not** exist $h(n)$ such that $\frac{f(n)}{\varepsilon(n)} \leq h(n) \leq f(n)$ and $DTIME(\frac{f(n)}{\varepsilon(n)}) \subsetneq DTIME(h(n)) \subsetneq DTIME(f(n))$.

In order to just show that, $DTIME(\frac{f(n)}{\varepsilon(n)}) \subsetneq DTIME(f(n))$ we need to use a stronger time hierarchy theorem and this is where we use the assumption that the number of tapes is fixed (we said two tapes above). See "The tight deterministic time hierarchy" by Martin Furer.

Since there are no computable natural number functions between $\frac{f(n)}{\varepsilon(n)}$ and $f(n)$ other than those that are $\Theta(f(n))$, we have that for every function $h(n)$ such that $\frac{f(n)}{\varepsilon(n)} \leq h(n) \leq f(n)$ and $h(n) \neq \Theta(f(n))$, $DTIME(\frac{f(n)}{\varepsilon(n)}) = DTIME(h(n))$.

> **Comments:**
> **username_2**: Yes, this is exactly what I had in mind too, but then got confused somewhere along the way. I just want to note, that $\epsilon(n)$ needn't be small at all; a similar argument shows that the lower function $\frac{f(n)}{\epsilon(n)}$ can be replaced with a function that is always either $f(n)$ or $0$, and the upper function $f(n)\epsilon(n)$ can be replaced with a function that is always either $f(n)$ or $\infty$.  
> **username_1**: @RickyDemer Yes, you are right!  Thank you very much for catching that.  I edited my answer to add the word unbounded.  :)  
> **username_1**: @username_2 Thank you very much for the comment!  Yes, I believe your right!  Neat!  :)  
> **username_0**: Im not entirely convinced about Claim 1. Consider $f_i(n) = 1$ if $n \leq i$, $n-i$ otherwise. Considering this enumeration, is $\epsilon(n) = \Theta(1)$?  
> **username_1**: @S.Pek Thank you for your question!  Yes, my previous construction wasn't so clear so I made some edits to my answer and hopefully it's a little more clear.  
> **username_1**: Basically $\varepsilon(n)$ will wait to grow until the first $i$ functions grow a little bit (that is surpass $i$).  Then, $\varepsilon(n)$ will sprout up 1 step.  Then, it waits to grow until the first $i+1$ functions have all grown a little bit and so on.  
> **username_1**: With your example, it seems that roughly for $n$ from 1 to $2 * i$, $\varepsilon(n)$ may be great than $f_i(n)$ and then for larger values of $n$, it will always be less.  
> **username_0**: I have two more concerns of this proof:  1) In claim 2 you said that the contradiction arises from the fact that there cannot exist a computable $\epsilon(n)$ as it equals $|h(n)-f(n)|$. I believe this to be a typographical error, as it should say there exist a $k'$ such that $\epsilon(n) = |h(n) - k'\cdot f(n)|$. But note that $k'$ need not be computable, so the argument need not hold.  2) You used the result by Furer in Claim 3. However, the result only holds for time-constructable functions, but $\frac{f(n)}{\epsilon(n)}$ need not be time-constructable.  
> **username_1**: @S.Pek Thank you!  I really appreciate your follow-up comments!  Yes, I will make some corrections with the above informal explanation for claim 2.  However, I believe that claim 3 is justified by Furer's result because if $f(n)$ is time constructible, then $DTIME(\frac{f(n)}{\varepsilon(n)}) \subseteq DTIME(o(f(n))) \subsetneq DTIME(f(n))$.  
> **username_1**: @S.Pek A correction to the previous comment, I meant to say since $\frac{f(n)}{\varepsilon(n)} = o(f(n))$, by Furer's work, we have that $DTIME(\frac{f(n)}{\varepsilon(n)}) \subsetneq DTIME(f(n))$.  
> **username_0**: I believe Furer's claim is that if $f,g$ time-constructable and $f(n) = o(g(n))$, then $DTIME(f(n)) \subsetneq DTIME(g(n))$. You seem to be implying something stronger, namely that it holds when $f,g$ are not time-constructable. This cannot be true, as it would violate Borodin's Gap Theorem.  
> **username_1**: @S.Pek Please correct me if I'm wrong, but I believe that it is still true if $g(n)$ is time-constructible.  (I do make the time-constructibility assumption in claim 3.  In other words, I assume that one side is time-constructible.)  
> **username_1**: The argument from Furer's paper seems to validate this claim that we only require that the larger of the two functions be time-constructible.  Please let me know if you find something wrong with this claim.  
> **username_1**: @S.Pek Hi again!  I revised the answer a bit.  I believe that claim 2 and claim 3 are up to par now.  I didn't write a formal proof, but I believe I included enough detail to be convincing.  Thanks again and please let me know if you have any comments, suggestions, concerns, or questions.  Thank you!  :)  

---

### Answer by username_3 on 2017-02-28. Score: 4

If this result is true, it would strengthen the best-known deterministic time hierarchy theorem. [This is more of a comment than an answer, but too long for a comment. It leaves open the direct construction of a counterexample.] Recall that the best Deterministic Time Hierarchy Theorem we currently have is that if $f(n), g(n)$ are time-constructible, and $g(n) \leq o( f(n) / \log f(n) )$, then $\mathsf{DTIME}(g(n)) \subsetneq \mathsf{DTIME}(f(n))$.

Now suppose your desired result is true, and let $g(n)$ be a time-constructible function that is close to, but still little-oh of, $f(n) / \log(f(n))$, say, $g(n) = f(n) / (\log f(n))^{3/2}$. (This $g$ may not be time-constructible for arbitrary time-constructible $f$, but surely for many time-constructible $f$ this $g$ is also time-constructible.) Now, your desired result produces an $h$ such that $\mathsf{DTIME}(g(n)) \subsetneq \mathsf{DTIME}(h(n)) \subsetneq \mathsf{DTIME}(f(n))$. In order to avoid improving the current-best time hierarchy theorem, we would need both $g(n) = o( h(n) / \log(h(n)) )$ and $h(n) = o(f(n) / \log(f(n))$. These two together imply that $g(n) \leq o( f(n) / (\log(f(n)) \log(h(n)))$. Since $h(n) \geq g(n)$, we have $g(n) \leq o( \frac{f(n)}{\log(f(n)) \log(g(n))})$, or equivalently $g(n) \log g(n) \leq o(f(n) / \log(f(n)))$. But $g(n) \log(g(n)) = f(n) / (\log(f(n))^{3/2} [\log(f(n)) - (3/2) \log \log(f(n)] \sim f(n) / \sqrt{\log(f(n))}$, which is not $o(f(n) / \log(f(n))$.

> **Comments:**
> **username_1**: Cool!  Also, note that there is a better time hierarchy theorem if the number of tapes is fixed.  See "The tight deterministic time hierarchy" by Martin Furer.  
> **username_3**: @MichaelWehar: Thanks for the pointer! Indeed, when one gets so tight as to only require $g(n) = o(f(n))$, as Furer shows when the number of tapes is fixed, then my argument goes away. (And for basically the same reason, my argument goes away if this question were about space hierarchy instead of time: for space we have a perfectly tight hierarchy theorem even if # tapes isn't fixed.)  

---

### Answer by username_4 on 2017-03-06. Score: 2

I think such a behaviour is true for 1-Tape-DTMs. On the one hand, we have $\mathrm{DTIME}\_1(O(n)) = \mathrm{DTIME}\_1(o(n \log n))$. Unfortunately, the only reference I know is in German: R. Reischuk, Einführung in die Komplexitätstheorie, Teubner, 1990, Theorem 3.1.8.

On the other hand, it should be possible to separate $\mathrm{DTIME}\_1(O(n))$ and $\mathrm{DTIME}\_1(O(n \log n))$ by the language $\{ x \#^{2^{|x|}} x \mid x \in \{0,1\}^\* \}$ using a standard crossing sequence argument.


---

