14
$\begingroup$

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

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

2 Answers 2

7
$\begingroup$

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).
$\endgroup$
3
  • 3
    $\begingroup$ it is worth pointing out that 1. holds for one-tape TMs only $\endgroup$ Jun 9, 2013 at 6:29
  • 2
    $\begingroup$ 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. $\endgroup$
    – Neal Young
    Mar 14 at 15:56
  • 1
    $\begingroup$ [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. $\endgroup$
    – Neal Young
    Mar 20 at 18:54
3
$\begingroup$

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$

$\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.