# Are runtime bounds decidable for anything nontrivial?

Problem  Given a Turing machine $M$ which has known runtime ${O}(g(n))$ with respect to input length $n$, is the runtime of $M \in {O}(f(n))$?

Is the above problem decidable for some nontrivial pairs of $g$ and $f$?A solution is trivial if $g(n) \in O(f(n))$.

This is related to the problem Are runtime bounds in P decidable? (answer: no). One can derive from Viola's answer that if $f(n)\not \in o(n)$ and $f(n)\not \in O(g(n))$ then the problem is undecidable.

The requirement that $f(n)\not \in o(n)$ is because the $M'$ in Viola's proof need $O(n)$ time to find its input size. Thus Viola's proof could not work when $f(n)=1$.

It would be interesting if we can decide on the run time of sublinear time algorithms. A special case is when we have arbitrary $g(n)$ and $f(n)=1$.

• Since the question you link to was very well received on CSTheory, you might want to flag for migration later.
– Juho
Jun 9, 2013 at 14:06
• Somewhat late to the game here, but I've added a more complete answer. Mar 20 at 18:53

Here are a few remarks which could be relevant:

1. Kobayashi proved that a TM running in time $o(n\log n)$ accepts a regular language (and so runs in time $O(n)$); recently this has been extended to non-deterministic TMs (Tadaki, Yamakami and Lin).
2. Machines running in time $o(n)$ actually run in constant time (consider any $n$ for which the running time is less than $n$; adding characters to the end doesn't affect the TM).
• it is worth pointing out that 1. holds for one-tape TMs only Jun 9, 2013 at 6:29
• In remark 1, how does it follow that, because a TM that accepts a regular language, it runs in time $O(n)$? Of course, there is another TM that accepts the same language that runs in time $O(n)$. But that doesn't seem to imply that the given TM runs in time $O(n)$. Is it known that there is no TM that runs in time, say, $\Theta(n \log(n) / \log \log n)$? Note that his has little to do with acceptance of any particular language. Mar 14 at 15:56
• [follow up] In turns out that Kobayashi's proof does essentially prove that any 1-tape TM running in time $o(n\log n)$ runs in time $O(n)$. See the answer I posted for more info. Mar 20 at 18:54

There are a few related posts and papers (summarized down below), but they don't quite answer this particular question. Here we mostly answer it. Consider the problem for an arbitrary pair of functions $$f$$ and $$g$$.

Theorem 1 (lower bounds). For multi-tape TMs, the problem is either trivial or undecidable.

For 1-tape TMs, if $$g(n) = \Omega(n\log n)$$, the problem is either trivial or undecidable.

Theorem 2 (upper bound). For 1-tape TMs, if $$g(n) = o(n\log n)$$, the problem is decidable.

The one main non-trivial decidable case is for 1-tape TMs when $$g(n) = n$$ and $$f(n) = 1$$.

The cases we leave open are for 1-tape TMs when $$g$$ is "ill-behaved" in that $$g$$ is neither $$O(n\log n)$$ nor $$\Omega(n \log n)$$, in other words, $$\lim\inf \frac{g(n)}{n\log n} = 0$$ and $$\lim\sup \frac{g(n)}{n\log n} = \infty$$.

Here are the decision problems we consider:

• $$H_{fg}$$: Given a multi-tape TM $$M$$ that runs in time $$O(g(n))$$, does $$M$$ run in time $$O(f(n))$$?

• $$H^1_{fg}$$: Given a single-tape TM $$M$$ that runs in time $$O(g(n))$$, does $$M$$ run in time $$O(f(n))$$?

Say that $$H_{fg}$$ is trivial unless

• some TM $$M$$ that runs in time $$O(g(n))$$ also runs in time $$O(f(n))$$,

• and some TM $$M$$ that runs in time $$O(g(n))$$ doesn't run in time $$O(f(n))$$.

Likewise for $$H^1_{fg}$$, but restricting "TM"s to 1-tape TMs.

The proof of Theorem 1 reduces the Halting problem to $$H_{fg}$$ and $$H^1_{fg}$$, similarly to several previous results, but with some new tricks to make sure the reduction produces a TM running in time $$O(g(n))$$. Theorem 2 follows easily from known upper bounds.

### Related work

Before we sketch the proofs, here is a summary of some related results. Note that OP's question has two distinctive properties: (i) it is about a promise problem (the given TM must run in $$O(g(n))$$ time), and (ii) it asks whether the TM runs in time $$O(f(n))$$. Most of the results published in traditional venues below are promise-free, and many concern exact (not big-$$O$$) bounds. The stack-exchange posts do consider promise problems. Informally, having a strong promise (small $$g$$), or having exact (as opposed to big-$$O$$) bounds for $$f$$ tends to reduce the computational complexity of $$H_{fg}.$$

It is an easy exercise to show that the problem "Given a TM $$M$$, does $$M$$ run in time $$O(1)$$?" is undecidable, whereas "Given a TM $$M$$ and a constant $$c$$, does $$M$$ run in time at most $$c$$?" is decidable.

• For many interesting functions $$f(n)$$ (e.g. $$f(n) = n+1$$) it is not decidable whether a given multi-tape TM runs in time $$f(n)$$ (note no $$O$$-notation!) [Hájek, 1979].

• Any of the following properties guarantees that the language of a given 1-tape TM $$M$$ is regular:

1. $$M$$ is deterministic and runs in time $$O(n)$$ [Hennie, 1965],
2. $$M$$ is deterministic and runs in time $$(o(n\log n))$$ [Hartmanis, 1968],
3. $$M$$ is non-deterministic with all execution paths running in time $$(o(n\log n))$$ [Kobayashi, 1985].
• From the proofs of those results it more or less follows that every 1-tape TM running in time $$o(n\log n)$$ runs in time $$O(n)$$ [Gajser, 2015], and that, given any linear function $$f(n)$$, it is decidable whether a given 1-tape TM runs in time $$f(n)$$ (note the absence of big-$$O$$ here!) [Gajser, 2019]. (In fact Gajser shows this is in co-NP.)

• Given a TM whose run-time is promised to be bounded by some (unknown) polynomial, one cannot compute an explicit polynomial bound [Math Overflow, 2010]. Similarly, given such a TM and integer $$k$$, it is undecidable whether the TM runs in time $$O(n^k)$$ [CS Theory stack-exchange, 2011]. The latter post cites [Hartmanis, 1989] as covering similar material.

### Utility lemma

Both proofs use the following utility lemma.

Lemma 1. If $$H_{fg}$$ or $$H^1_{fg}$$ is not trivial, then $$f(n) = \Omega(1)$$ and $$g(n) = \Omega(n)$$.

Proof. Assume $$H_{fg}$$ is not trivial. Some TM runs in time $$O(f(n))$$, so $$f(n)$$ and $$g(n)$$ are $$\Omega(1)$$. Let $$t(n)$$ be the run time of some TM such that $$t(n)$$ is $$O(g(n))$$ but not $$O(f(n))$$. As observed in e.g. Lemma 3.1 [Gajser, 2015] if $$t(n_0) \le n_0$$ for any $$n_0$$, then it must be that $$t(n) = O(1) = O(f(n))$$ (because on inputs of size $$n_0$$ the TM's tape head never leaves the input, so the TM also halts in at most $$n_0$$ steps on any larger input). So $$g(n)$$ must be $$\Omega(n)$$. This proves Lemma 1 for $$H_{fg}$$. The same proof (but restricted to 1-tape TMs) works for $$H^1_{fg}$$ $$~~~\Box$$

### Proof sketch for Theorem 1

First consider $$H_{fg}$$. Assume $$H_{fg}$$ is not trivial. Let $$M_g$$ be a TM with run-time in $$O(g(n))$$ but not $$O(f(n))$$. Our goal is to make the natural reduction from the Halting problem to $$H_{fg}$$ work. Given a 1-tape DTM $$M$$, the reduction outputs a $$2$$-tape DTM $$M'$$ that does the following:

TM $$M'$$ on input $$x$$ of length $$n=|x|$$:

1. simulate $$M$$ on empty input until it halts or completes some $$\Theta(n)$$ steps, whichever comes first
2. if $$M$$ doesn't halt during that simulation, then simulate $$M_g$$ on input $$x$$ until $$M_g$$ halts

The implementation will ensure that the run time of $$M'$$ is always $$O(g(n))$$, and is $$O(f(n))$$ if and only if $$M$$ halts.

##### Implementation details and proof of correctness for $$H_{fg}$$

Step 1 holds $$x$$ on its first tape while using its second tape to simulate $$M$$. Meanwhile, just before each simulated step of $$M$$, Step 1 moves the head of the first tape one cell to the right (thus using this head as a counter). Step 1 halts the simulation when $$M$$ halts or when the head of the first tape moves off of $$x$$. Step 1 then returns the head of the first tape to cell 1 of that tape. Step 2 of $$M'$$ then simulates $$M_g$$ on input $$x$$ using just the first tape. This completes the reduction.

To see that it's correct, first consider the case that $$M$$ halts on empty input, in some $$h$$ steps. Note that $$h=O(1)$$, that is, it is independent of $$x$$. Step 1 of $$M'$$ then runs in time $$O(\min(h, n)) = O(1)$$. Step 2 of $$M'$$ only runs if $$n\le h = O(1)$$, so runs in time $$O(\max_{n \le h} g(n)) = O(1)$$. So, in the case that $$M$$ halts on empty input, $$M'$$ runs in time $$O(1)$$. By Lemma 1 this is $$O(f(h))$$ and $$O(g(h))$$. So, if $$M$$ halts on empty input, then $$M'$$ runs in time $$O(f(h))$$ and $$O(g(h))$$.

Next consider the case that $$M$$ never halts. Step 1 of $$M'$$ takes $$O(n=|x|)$$ time. Step 2 then takes $$O(g(n))$$ time. So $$M'$$ runs in time $$O(g(n) + n)$$. By Lemma 2 this is $$O(g(n))$$. So, if $$M$$ doesn't halt on empty input, then $$M'$$ runs in time $$O(g(n))$$.

So $$M$$ always runs in time $$O(g(n))$$, and runs in time $$O(f(n))$$ iff $$M$$ halts on empty input. So the reduction is correct in the case $$k\ge 2$$. This proves Theorem 1 for this case.

##### Implementation details and proof of correctness for $$H^1_{fg}$$

Assume $$H^1_{fg}$$ is not trivial. Assume (per the theorem statement) that $$g(n) = \Omega(n\log n).$$ The proof is the same as for $$H_{fg}$$, except that $$M'$$ implements Step 1 differently, as follows, using only the one available tape.

Step 1 of $$M'$$ will simulate $$M$$, meanwhile counting the number $$t$$ of simulated steps, and somehow detecting when (if) $$t$$ reaches $$\Omega(n)$$. The challenge is to do such a simulation with a slowdown of at most an $$O(\log n)$$ factor. That is, $$M'$$ should simulate the first $$t$$ steps of $$M$$ in $$O(t \log t)$$ time.

Throughout the simulation, we think of $$M'$$ as having three virtual tapes, sharing one common tape head. The first virtual tape holds $$x$$. This virtual tape is read-only during Step 1. The second virtual tape is used as the simulated tape of $$M$$. The third tape is used as a "work" tape for $$M'$$ to hold additional state as described below. (Each tape cell is initialized lazily, only when, in the course of the computation as described below, $$M'$$ encounters the cell. These virtual cells are implemented by introducing appropriate symbols into the tape alphabet of $$M'$$ in a standard way.)

As $$M'$$ simulates $$M$$, it stores on its work tape, just to the right of the tape head, a counter that holds the number $$t$$ of steps simulated so far. It encodes $$t$$ in binary, using $$O(\log t)$$ bits. Each time $$M'$$ simulates a step of $$M$$, it also increments $$t$$. Each increment takes $$O(\log t)$$ time, including the time to reposition $$t$$ to keep it just to the right of the tape head. This effectively slows the simulation by an $$O(\log t)$$ factor.

Also, each time $$t$$ passes a power of two, $$M'$$ pauses the simulation temporarily and does a probe. The probe moves the tape head $$t$$ steps to the right, looking for the end of the original input $$x$$. If it finds the end within $$t$$ steps, it knows that $$n= \Theta(t)$$, so it stops the simulation (and restores the tape to its original state for Step 2).

In order to look $$t$$ steps to the right, as $$M'$$ moves the tape head to the right, it brings along a "countdown" value $$t'$$, encoded in binary and held just to the right of the tape head. The probe initializes $$t'=t$$, then, with each step to the right, decrements $$t'$$ and shifts it one step to the right. If $$t'$$ reaches zero before the probe finds the end of $$x$$, the probe stops and returns the head to resume the simulation of $$M$$. Note that probing $$t$$ cells to the right in this way takes time $$O(t\log t)$$.

This completes the description of $$M'$$. Next we verify that the reduction is correct.

Using the probes, $$M'$$ ensures that $$t = O(n)$$ throughout the simulation, and that the simulation halts when $$t = \Theta(n)$$.

A probe (after $$t$$ simulated steps) takes $$O(t\log t)$$ steps. So the total time for $$M'$$ to simulate the first $$t$$ steps of $$M$$ is at most:

\begin{align} &O(t \log t) && \text{for simulating the } t \text{ individual steps, plus} \\ &+O(t \log t + \frac{t}{2} \log \frac{t}{2} + \frac{t}{4}\log \frac{t}{4} + \cdots) && \text{for the } {\log_2 t} \text{ probes, making} \\ &=O(t\log t) && \text{total.} \end{align}

Suppose that $$M$$ halts on empty input, in, say, some $$h$$ steps. So $$h=O(1)$$ (independent of $$x$$). There are $$O(2^h) = O(1)$$ inputs of length $$O(h)$$, so the time for those is $$O(1)$$. For inputs with length $$n = \Omega(h)$$, the simulation will stop when $$M$$ halts, so will take time $$O(h \log h) = O(1)$$. Step 2 then does nothing. So, if $$M$$ halts, then $$M'$$ runs in time $$O(h\log h) = O(1)$$. This is $$O(f(n))$$ and $$O(g(n))$$ (as required) by Lemma 1. So the reduction is correct in this case.

In the case that $$M$$ never halts, Step 1 of $$M'$$ stops the simulation after $$O(n)$$ steps, so Step 1 takes $$O(n\log n)$$ time. Step 2 then takes $$O(g(n))$$ time. So in this case $$M'$$ takes time $$O(n\log n + g(n))$$. By assumption $$g(n) = \Omega(n\log n)$$, so this is $$O(g(n))$$. So the reduction is correct in this case. This proves Theorem 1. $$~~~~\Box$$

### Proof sketch for Theorem 2

Assume per the theorem statement that $$g(n) = o(n\log n)$$. By e.g. [Gajser, 2015] and Lemma 1, any 1-tape TM running in time $$o(n\log n)$$ runs either in time $$\Theta(1)$$ or time $$\Theta(n)$$. Also, $$f(n) \ne O(g(n))$$ (else the problem is trivial). So assume WLOG that $$f(n) = \Theta(1)$$ and $$g(n) = \Theta(n)$$.

By a result of [Gajser, 2019], given any constant $$a \ge 1$$ and 1-tape TM $$M$$, it is decidable whether $$M$$ finishes in at most $$cn$$ steps (on all $$n$$, for all inputs of length $$n$$). Further, given a 1-tape TM that runs in time at most $$cn$$, one can explicitly compute, from $$M$$ and $$c$$, a DFA $$D$$ such that the language of $$D$$ contains exactly the sequences of crossing sequences that represent accepting computations of $$M.$$

(Each crossing sequence has length $$O(1)$$. The symbols in the input alphabet for $$D$$ correspond to pairs $$(\alpha, s)$$, where $$\alpha$$ is an input symbol for $$M$$, and $$s$$ is a possible crossing sequence.)

Finally, here is the procedure for deciding, given a 1-tape TM $$M$$ that runs in time $$O(g(n)) = O(n)$$, whether $$M$$ runs in time $$O(f(n)) = O(1)$$:

1. Compute a $$c$$ such that $$M$$ runs in time $$c n$$. (Use Gajser's result with $$c=1,2,\ldots$$ to find the smallest such $$c$$.)

2. From $$M$$ and $$c$$, use Gajser's other result to compute a DFA $$D$$ such that the language of $$D$$ contains exactly those sequences that represent computations of $$M$$.

3. Return 'yes' (i.e., that $$M$$ runs in time $$O(f(n))$$) if $$L(D)$$ is finite, else return 'no'. (This is decidable given $$D$$.) $$~~~~\Box$$