8
$\begingroup$

The question:

Is there an $f$ in $\omega(n) \cap o(n \log n)$ that is time-constructible on a 1-tape DTM?

I.e. $f$ such that $\lim_{n\to\infty} \frac{n}{f(n)} = \lim_{n\to\infty} \frac{f(n)}{n \log n} = 0$?

Discussion:

Consider 1-tape deterministic TM's that take inputs of the form $1^n$.

It is easy to design such a TM with running time $\Theta(n)$: just scan the input once.

It is easy to design such a TM with running time $\Theta(n\log n)$: make repeated passes over the tape, each pass replacing every other 1 with a 0, and halting if the pass finds no 1's.

The question is, is there a TM whose asymptotic running time $t(n)$ is strictly between these two? That is, $t(n)$ is $\omega(n)$ but $o(n\log n)$? Eg. $t(n) = \Theta(n\log \log n)$?

Answer (added in an edit):

The answer (posted below) is no. The proof is an adaption of the proof of a closely related result: that any 1-tape TM that runs in $o(n\log n)$ time accepts a regular language. The proof uses a crossing-sequence argument.


[EDIT: This result was observed in Corollary 4.6 of the following paper:

Gajser, David, Verifying time complexity of Turing machines, Theor. Comput. Sci. 600, 86-97 (2015). ZBL1329.68111.]


Context:

This question comes up in trying to answer another question, namely, the complexity of deciding (for fixed $f$ and $g$ with $g(n) \not\in O(f(n)$) whether a given 1-tape TM $M$ that is promised to run in time $O(g(n))$ in fact runs in time $O(f(n))$). Variants of this are considered here, here, and here. In the cases where $g(n) = O(f(n)\log n)$, or when $f(n) = \Theta(n)$, for 1-tape TM's this logarithmic gap presents an apparent obstacle to proving undecidability via diagonalization.

This answer claims "most functions that we deal with in practice turn out to be time constructible." On the other hand, it is not hard to see that there is no time-constructible function in $\omega(1) \cap o(n)$, because, if a TM doesn't take more than $n_0$ steps given input $1^{n_0}$, then it doesn't look past the final input cell $n_0$, so, given any larger input, the TM also doesn't look past tape cell $n_0$, and its behavior must be the same as on input $1^{n_0}$. So its run time never exceeds $O(\max_{n\le n_0} t(n)) = O(1)$ (where $t(n)$ is the run time on inputs of size $n$).

The Gap Theorem says that, for any function $f$ with $f(n)\ge n$, there is a $g$ such that $\textsf{DTIME}(g(n)) = \textsf{DTIME}(f(g(n))$, although if $g$ is required to be time constructible, the Time Hierarchy Theorem says that $\textsf{DTIME}(o(g(n))) \ne \textsf{DTIME}(g(n)\log n)$.

As Emil points out, it is easy to show that, e.g., $n\log\log n$ is time-constructible using multi-tape TMs, which as Chandra points out are usually the basis for definitions of space/time complexity, especially for low complexity classes. Here the question is specifically about 1-tape TM's.

$\endgroup$
9
  • 1
    $\begingroup$ But how to cut down to sqrt in one (linear time) pass, @JoshuaGrochow? $\endgroup$
    – Neal Young
    Commented Mar 15 at 1:16
  • 1
    $\begingroup$ Yeah I was thinking about that - that's why I wrote it as a comment instead of an answer ;). $\endgroup$ Commented Mar 15 at 1:46
  • 5
    $\begingroup$ Don't we normally use multi-tape TMs when defining time/space complexity? Do you specifically want to restrict attention to 1-tape TMs? $\endgroup$ Commented Mar 15 at 2:14
  • 3
    $\begingroup$ On a 2-tape TM, it's straightforward: using a binary counter, compute the binary representation of $n$ in one $O(n)$ pass over the input, compute the binary representation of $f(n)$ in time, say, $n^\epsilon$ for $\epsilon<1$ (any remotely sensible function you'd want to use as a time bound should be computable in subexponential time), and convert it back to unary in time $O(f(n))$. $\endgroup$ Commented Mar 15 at 8:30
  • 2
    $\begingroup$ @ChandraChekuri - I do specifically have in mind 1-tape TM's. For multi-tape TM's I agree there is no issue, and I agree that it seems to be customary to use multi-tape TM's for defining time/space complexity , e.g. per Wikipedia DTIME is usually defined w.r.t. multi-tape TMs. $\endgroup$
    – Neal Young
    Commented Mar 15 at 13:16

1 Answer 1

5
$\begingroup$

[EDIT: This result was already observed in Corollary 4.6 of the following paper:

Gajser, David, Verifying time complexity of Turing machines, Theor. Comput. Sci. 600, 86-97 (2015). ZBL1329.68111.]



Theorem 3.3 in [1] shows that the language of any 1-tape $o(n\log n)$-time DTM is regular. Adapting their proof gives the following negative answer to my question. (I should note that [1] in turn adapted the proof of Theorem 3 of [2].)

Let $M$ be any 1-tape DTM. Let $f(n)$ be its worst-case run time on inputs of length $n$.

Lemma 1. If $f(n) = o(n\log n)$, then $f(n) = O(n)$.

Proof sketch. Assume that $f(n) = o(n\log n)$. Apply the proof of Theorem 3.3 of [1] to $M$. (Just to use the proof in [1], assume WLOG that $L(M) = \Sigma^*$; if not make it so by replacing every undefined (i.e. halting) transition in $M$ by a transition to an accept state.)

For some constant $c_M$ depending only on $M$, that proof shows that

The length of any crossing sequence of $M$ for any input $x$ with $|x|\ge 2$ is at most $c_M$.

This immediately implies that, on any input of length $n$, the number of steps that $M$ takes with its tape head over the first $n-1$ tape cells is $O(c_M n) = O(n)$. To finish, we observe that the number of steps that $M$ takes with its tape head over the remaining cells is $O(1)$.

Indeed, let $\mathcal X$ be the set of possible crossing sequences that can occur between cells $n-1$ and $n$ in any execution of $M$ on any input. Let $\Sigma$ be $M$'s tape alphabet. Note that $|X|$ and $|\Sigma|$ are both $O(1)$, as $M$ is fixed and every sequence in $X$ has length at most $c_M$.

For $(X, a) \in \mathcal X \times \Sigma$, let $T(X, a)$ be the the time spent by $M$ over tape cells $n, n+1, n+2, \ldots$ given that the crossing sequence between tape cells $n-1$ and $n$ is $X$, and tape cell $n$ initially holds $a$ (that is, $x_n=a$). Note that the behavior of $M$ beyond tape cell $n$ is fully determined by this $X$ and $a$, and each $T(X, a)$ is finite because $M$ always terminates.

Then, on any input, the time spent by $M$ over tape cells $n+1, n+2, \ldots$ is at most $\max_{(X, a) \in \mathcal X \times \Sigma } T(X, a)$. This is $O(1)$, as the maximum is over $O(1)$ values, each of which is $O(1)$. $~~~~\Box$

Remark. I wonder whether the proof (in particular, the proof of [1]) can be made to work assuming only $t(n) \ne O(n\log n)$.


[1] Kobayashi, Kojiro, On the structure of one-tape nondeterministic Turing machine time hierarchy, Theor. Comput. Sci. 40, 175-193 (1985). ZBL0603.68047.

[2] Hennie, F. C., One-tape, off-line Turing machine computations, Inform. and Control 8 (1965), 553-578 (1966); Russian translation in Probl. Mat. Logiki. Slozn. Algoritm. Klassy Vychisl. Funkcii, 223-248 (1970). ZBL0231.02048.

$\endgroup$
6
  • $\begingroup$ I'm not sure I understand what you mean by "otherwise just make every state an accepting state". Then the machine halts in time $t(n)=1$ on every input, doesn't it? And why do you actually need the assumption $L(M)=\Sigma^*$, anyway? $\endgroup$ Commented Mar 15 at 17:43
  • 1
    $\begingroup$ I don't see how "$M$ always terminates" should imply that $T(X,a)$ is finite for all $X$ and $a$. Surely it is possible that some pair $(X,a)$ cannot occur in any run of $M$? But anyway, this should not matter: simply take the maximum over those $T(X,a)$ that are finite. The infinite ones are irrelevant, as they cannot occur in the run of $M$ on any input $x$ (which is assumed to terminate, in $o(n\log n)$ steps). $\endgroup$ Commented Mar 15 at 17:48
  • $\begingroup$ Yes, good catch. I had in mind that $\mathcal X$ should be the set of crossing sequences that can actually occur there for $M$. $\endgroup$
    – Neal Young
    Commented Mar 15 at 18:07
  • $\begingroup$ @EmilJeřábek, re "make every state an accepting state", in the definition of TM that I am using (see e.g. Wikipedia) the TM halts when (and only when) the transition table of the TM doesn't have a suitable entry, and then (and only then) the input is accepted if the current state is an accept state. I want every input to be in the language because the proof of Theorem 3.3 in [1] only considers inputs in $L(M)$ (although that assumption is not really used in the proof). $\endgroup$
    – Neal Young
    Commented Mar 15 at 18:12
  • 1
    $\begingroup$ That’s a rather unusual convention. Usual definitions make the machine halt immediately after it enters an accepting (or rejecting, in formalisms that have them) state. The definition on Wikipedia, which ostensibly comes from Hopcroft and Ullman (I haven’t checked), requires exactly that: you must have missed the indicated domain of $\delta$, and the accompanying footnote. The definition in Sipser also works this way, though it differs in other details. $\endgroup$ Commented Mar 15 at 19:43

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.