6
$\begingroup$

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

Improve this question
$\endgroup$
8
  • $\begingroup$ there's something missing in the second sentence: "a TM deciding A in time $O(n\log n)$"? $\endgroup$
    – Marcus Ritt
    Commented Dec 4, 2010 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$
    – Ryan Williams
    Commented Dec 4, 2010 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$
    – Ryan Williams
    Commented Dec 4, 2010 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
    Commented Dec 4, 2010 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
    Commented Dec 5, 2010 at 1:24

1 Answer 1

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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