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))$

  • $\begingroup$ there's something missing in the second sentence: "a TM deciding A in time $O(n\log n)$"? $\endgroup$ Dec 4 '10 at 12:24
  • 6
    $\begingroup$ "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. $\endgroup$ Dec 4 '10 at 13:08
  • 6
    $\begingroup$ 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. $\endgroup$ Dec 4 '10 at 13:09
  • 1
    $\begingroup$ @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))$.) $\endgroup$
    – Kaveh
    Dec 4 '10 at 14:48
  • 1
    $\begingroup$ 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 en.wikipedia.org/wiki/Regular_language a somewhat different argument is given, in terms of DSPACE. $\endgroup$
    – chazisop
    Dec 5 '10 at 1:24

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.