<p>I will try to answer the question more generally so does not depend on the specific problem. Let $L$ be a language in $DTime(O(t(n))-DTime(o(t(n))$. Can we use padding to get a language in  $DTime(O(s(n))-DTime(o(s(n))$ where $s(n) \in \Omega(t(n))$ is an arbitrary (time constructible) function?</p>

<p>The answer is no:</p>

<blockquote>
  <p>the complexity class separations using padding translate downwards but not upwards, see <a href="https://cstheory.stackexchange.com/questions/2434/why-do-equalities-between-complexity-classes-translate-upwards-and-not-downwards">Why do equalities between complexity classes translate upwards and not downwards?</a>.</p>
</blockquote>

CC BY-SA 2.5
2010-12-04T15:01:44.743Z
2010-12-04T15:14:47.030Z
2017-04-13T12:32:28.743Z
Kaveh
<p>Consider the language $A=\{0^{k}1^{k}|k\geq0\}$ . On Sipser's book "Introduction to the Theory of Computation" an algorithm with running time $O(n\log n)$ is given, on single-tape TM. We also know that the set of languages that run in time $o(n\log n)$ is exactly the set of regular languages. Since $A$ is not a regular language, we can be sure that this is a strict lower bound, on a single-tape TM.</p>

<p>Therefore, if $f(x) = n\log n$ and $g(x) = o(f(x))$ , the existence of this language allows us to say that 
$DTIME(g(x)) \subset DTIME(f(x))$ . Therefore:</p>

<p>By using the padding argument, couldn't we argue that for any time function $h(x) = \Omega(n\log n) $ the same result applies, i.e. that if $g(x) = o(h(x))$ then $DTIME(g(x)) \subset DTIME(h(x))$
</p>

CC BY-SA 2.5
2010-12-04T12:24:11.293Z
there's something missing in the second sentence: "a TM deciding A in time $O(n\log n)$"?
Marcus Ritt
CC BY-SA 2.5
2010-12-04T12:27:05.100Z
Be careful about these lowerbounds, they usually depend on the exact details of the TM model being used. Some clarification questions:
is there a comma missing between $n\log n$ and $g(x)$ in the second paragraph?  What do you mean by a strict lowerbound, you have given an upperbound. And could you please spell out "the same result" for general $h$?
Kaveh
CC BY-SA 2.5
2010-12-04T13:08:50.400Z
"Since $A$ is not a regular language this is a strict lower bound." This isn't true. On (for example) a two-tape Turing machine, $A$ is in $O(n)$ time.
Ryan Williams
CC BY-SA 2.5
2010-12-04T13:09:35.703Z
Let one tape hold input. If the input starts with $1$, reject. On the 2nd tape, copy over $0$'s in the input, moving the input head right, until input head reads $1$. (If it sees blank first then reject.) For each $1$ the input head sees, move 2nd tape head to the left for one square as the input head moves to the right. If the input ever sees another $0$, reject. If the 2nd tape head reaches its leftmost cell precisely when the input head runs out of $1$'s, accept, otherwise reject.
Ryan Williams
CC BY-SA 2.5
2010-12-04T14:18:33.640Z
Thanks for the corrections. I should say that I am interested in single tape TMs, since I am interested in the time hierarchy theorem.
chazisop
CC BY-SA 2.5
2010-12-04T14:48:17.137Z
@chazisop: Time hierarchy theorems hold for many tape machines also, the point about the model is that these lowerbounds usually exploit specific restrictions of the model used to prove lowerbounds and are not very robust and therefore fail to work with slight changes. ps: I didn't know that $DTime(o(n \log n))$ is exactly the regular languages, can you give a reference for it? (it seems a little bit strange because $REG=DSpace(0) \subseteq DTime(n)$, so if I am not making a mistake what you say implies that there is no language between real time and $DTime(o(n \log n))$.)
Kaveh
CC BY-SA 2.5
2010-12-05T01:24:31.980Z
The reference is Sipser's book (chapter 7) , where this language and algorithm come from. Problem 7.47 also asks for a proof of this statement. Also in http://en.wikipedia.org/wiki/Regular_language a somewhat different argument is given, in terms of DSPACE.
chazisop
CC BY-SA 2.5
2010-12-05T06:40:06.527Z
Thanks, I checked it and found the reference, it is Trakhtenbrot (1964) and Hartmanis (1968) which states that any language not in $DTime(n)$ needs (deterministic) time at least $n \log n$ (on these machines), so there is a gap there (but as I said in my answer the padding arguments only translate gaps/separations downwards.)
Kaveh
<cc.complexity-theory><time-hierarchy><padding>
Lower bounds and class separation
chazisop
# Lower bounds and class separation

(Asked by: username_0 on 2010-12-04)

Consider the language $A=\{0^{k}1^{k}|k\geq0\}$ . On Sipser's book "Introduction to the Theory of Computation" an algorithm with running time $O(n\log n)$ is given, on single-tape TM. We also know that the set of languages that run in time $o(n\log n)$ is exactly the set of regular languages. Since $A$ is not a regular language, we can be sure that this is a strict lower bound, on a single-tape TM.

Therefore, if $f(x) = n\log n$ and $g(x) = o(f(x))$ , the existence of this language allows us to say that
$DTIME(g(x)) \subset DTIME(f(x))$ . Therefore:

By using the padding argument, couldn't we argue that for any time function $h(x) = \Omega(n\log n) $ the same result applies, i.e. that if $g(x) = o(h(x))$ then $DTIME(g(x)) \subset DTIME(h(x))$

**Tags:** cc.complexity-theory, time-hierarchy, padding
> **Comments:**
> **username_1**: there's something missing in the second sentence: "a TM deciding A in time $O(n\log n)$"?  
> **username_2**: Be careful about these lowerbounds, they usually depend on the exact details of the TM model being used. Some clarification questions: is there a comma missing between $n\log n$ and $g(x)$ in the second paragraph?  What do you mean by a strict lowerbound, you have given an upperbound. And could you please spell out "the same result" for general $h$?  
> **username_3**: "Since $A$ is not a regular language this is a strict lower bound." This isn't true. On (for example) a two-tape Turing machine, $A$ is in $O(n)$ time.  
> **username_3**: Let one tape hold input. If the input starts with $1$, reject. On the 2nd tape, copy over $0$'s in the input, moving the input head right, until input head reads $1$. (If it sees blank first then reject.) For each $1$ the input head sees, move 2nd tape head to the left for one square as the input head moves to the right. If the input ever sees another $0$, reject. If the 2nd tape head reaches its leftmost cell precisely when the input head runs out of $1$'s, accept, otherwise reject.  
> **username_0**: Thanks for the corrections. I should say that I am interested in single tape TMs, since I am interested in the time hierarchy theorem.  
> **username_2**: @chazisop: Time hierarchy theorems hold for many tape machines also, the point about the model is that these lowerbounds usually exploit specific restrictions of the model used to prove lowerbounds and are not very robust and therefore fail to work with slight changes. ps: I didn't know that $DTime(o(n \log n))$ is exactly the regular languages, can you give a reference for it? (it seems a little bit strange because $REG=DSpace(0) \subseteq DTime(n)$, so if I am not making a mistake what you say implies that there is no language between real time and $DTime(o(n \log n))$.)  
> **username_0**: The reference is Sipser's book (chapter 7) , where this language and algorithm come from. Problem 7.47 also asks for a proof of this statement. Also in http://en.wikipedia.org/wiki/Regular_language a somewhat different argument is given, in terms of DSPACE.  
> **username_2**: Thanks, I checked it and found the reference, it is Trakhtenbrot (1964) and Hartmanis (1968) which states that any language not in $DTime(n)$ needs (deterministic) time at least $n \log n$ (on these machines), so there is a gap there (but as I said in my answer the padding arguments only translate gaps/separations downwards.)  

---

## 1 answers

### Answer by username_2 on 2010-12-04. Score: 5 | Accepted answer

I will try to answer the question more generally so does not depend on the specific problem. Let $L$ be a language in $DTime(O(t(n))-DTime(o(t(n))$. Can we use padding to get a language in $DTime(O(s(n))-DTime(o(s(n))$ where $s(n) \in \Omega(t(n))$ is an arbitrary (time constructible) function?

The answer is no:

> the complexity class separations using padding translate downwards but not upwards, see [Why do equalities between complexity classes translate upwards and not downwards?](https://cstheory.stackexchange.com/questions/2434/why-do-equalities-between-complexity-classes-translate-upwards-and-not-downwards).


---

