Examples of quasilinear vs. essentially linear time translatable models

Question

The Hennie-Stearns theorem says that $k$-tape Turing machines with $k \ge 2$ are intertranslatable with loglinear blowup ($O(t \times \log{(t)}$).

This would define an equivalence class of models, except that loglinear blowup is not closed under composition. So if we really want to abstract away from Turing machines, we'll have to consider at least quasilinear ($t \times \log{(t)}^{O(1)}$) blowup, which is transitively closed.

However, we also have a transitive closure under essentially linear blowup ($t^{1+o(1)}$).

Both classes preserve the exponent of polynomial-time algorithms and the base of exponential-time algorithms.

My overall question is, what are the qualitative differences between these two classes and which is the more natural one to study (in terms of physical or other intuition)?

And more specifically, what is an example of a model that is translatable to a multi-tape machine in essentially linear time but not quasilinear time, or in the other direction? I know we can construct one artificially by changing the definition of a time step, but I'm hoping for something that yields more insight.

One example I came up with that illustrates the difference is an algorithm that counts all $n$-bit strings satisfying some polynomial-time test. This runs in $2^n \times n^{O(1)}$ time, which is preserved by a quasilinear blowup, but after an essentially linear time translation that becomes $2^{n} \times 2^{o(n)}$, meaning that it takes more than a polynomial to test each bit string on average, even though in the same model we can still test a single string in polynomial time. I'm imagining this explained by a machine that experiences random errors and is only expected to be right more than half the time; in order to usually guess the right count, it will have to be virtually certain about the presence or absence of each of the $2^n$ strings, that's why it spends more time on each string on average than the polynomial-time test that only has to be right $51\%$ of the time.

[EDIT: I think there are too many errors in the below for it to be useful. I'm still trying to develop the same idea, a machine that has too much trouble keeping track of a count to be translatable in quasilinear time.]

Let me expand on that because it seems to be approaching what I'm looking for. Suppose an error-prone machine is one such that, with a fixed probability $p$, an attempt to change a value on any working tape fails. If it writes the existing value back that always works. Halting with an output means halting strictly more than half the time with the same output, and halting within a certain time means always halting within that time. The latter definition means that if we write each bit by sitting in a loop until it is correct, then the time becomes unbounded; this lets us simulate an ordinary Turing machine, but not with any time translation. But we can simulate an ordinary machine on the error-prone machine up to $t$ steps by writing every bit $b(t)$ times, making its probability of being incorrect $p^{b(t)}$. There is a $b(t) \in O(\log{(t)})$ sufficient to operate perfectly for $t$ steps more than half the time, and $t \times b(t)$ is only loglinear, but for a time translation we need a universal machine and in that situation we're not given $t$ in advance. So what I'm curious about now is how tightly we can constrain the time translation factor and still be correct half the time, and whether we can use something like this to characterize essentially linear time translations vs. quasilinear ones.

I believe I can demonstrate that this model has a time translation in $O(t^k)$ for every $k>1$. Dedicate a working tape to keeping track of the number of times our universal machine is to repeat each emulated step. It contains a string of ones delimited by blanks at the ends. The outer loop of the universal machine walks the list of ones from left to right, attempting to repeat the same emulation step in between movements. When it reaches the end, it attempts to write another one, and then resets itself by walking back to the left end, finally advancing to the next emulation step. This seems like more than enough repeats to be half-correct, and we're effectively taking $b(n) \approx (1-p) \times n$ resulting in an essentially quadratic time translation. We can generalize this by adding another counter tape to control the extension of the first one, bringing the time translation down to $O(t^{\frac{3}{2}+o(1)})$, and repeating this gives us any superlinear polynomial bound. Is it possible to bring this down to quasi- or essentially linear?

Answer 1

I will start with an overall comparison of essentially linear v quasilinear, and then give a specific example of the requested computational models.

As an equivalence relation, quasilinear time (denoted using $\tilde{O}$) is the most fine-grained measure that is robust between a number of different sequential deterministic models. By contrast, essentially linear time is the coarsest uniform measure that preserves the polynomial exponent.

Two common classes of quasilinear time

I should note that even for essentially linear time, there are two commonly used classes of models that are not known to be equivalent:

1. Multitape Turing machines, 2-tape machines, one-tape and a stack (even with oblivious movement), sufficiently uniform circuits.

2. RAM-based machines (with variations on the cost of a memory access), Turing machines on binary trees, and related models.

Notes:
* In both classes, the models separated by a comma are quasilinear time equivalent.
* Most fine-grained complexity results in literature use RAM-based machines.
* Multitape Turing machines with two-dimensional tapes appear to be intermediate between (1) and (2).
* If our computational model is Turing machines with multidimensional tapes (with the dimension arbitrary and dependent on the machine), then it is equivalent to RAM-based machines under $O(n^{1+ε})$ reducibility for every $ε>0$ (even for single tape machines), but as far as we know, not under quasilinear or $O(n^{1+o(1)})$ reducibility.

Quasilinear v essentially linear algorithms/reductions

Quasilinear time is more frequently used than essentially linear time because it is more precise and because the extra precision often comes for free. Partly related to near-absence of natural half-exponential growth rates, run times often take a specific form, such as $a^n n^{O(1)}$ or $n^b \log(n)^{O(1)}$, and in these cases using $\tilde{O}(a^n)$ and $\tilde{O}(n^b)$ is more precise than giving the times up to an essentially linear factor. (A notational caveat: some authors would only use $\tilde{O}(a^n)$ for time $a^n (\log n)^{O(1)}$.)

However, some algorithms have a more complicated run time:
- A $2^{(\log n)^c}$ multiplicative factor is inverse quasipolynomial for $0 < c < 1$, and is essentially linear but not quasilinear. It is the most common example of such times.
- For APSP (all pairs shortest paths) we have a more than quasilinear speed up over $O(n^3)$ but no known $O(n^{3-ε})$ algorithm, and similarly for problems that are in a certain specific sense reducible to APSP.
- Known CNF SAT algorithms have a more than quasilinear speed over simple complete search time (note that formula length is polynomial in the number of input variables and polylogarithmic in the search time), but under a variant of SETH (Strong Exponential Time Hypothesis) cannot have (in the worst case) more than an essentially linear speed up. For Formula SAT, we only have a quasilinear speed up.

A specific example

We will use Turing machines and circuits in what may be described as a weakly infinite-dimensional tape/space. In one example, each point is a sequence $x_1,x_2,...$ of natural numbers such that $x_{i+1}≤x_i/2$. Alternatively, we could have used $x_i/k$ (rational constant $k>1$), or something else, the main point is that it is a sufficiently efficiently computable space whose proximity is more than polynomial but is quasipolynomial rather than exponential. For navigating the space using a finite internal state, we can include the movement dimension in the external state and have a command to cycle through available dimensions.

Now, a single head/tape Turing machine on such a space can simulate ordinary multitape machines and even RAM-based machines in essentially linear but not quasilinear time. The impossibility proof uses a simple communication complexity argument. It is open whether multitape or multihead Turing machines on such spaces are quasilinear time equivalent to ordinary multitape Turing machines, or RAM-based machines, or both, or are strictly intermediate in power.

Sufficiently uniform circuits in such a space can simulate multitape Turing machines in essentially linear but not quasilinear time if by time for a circuit we mean circuit size rather than depth. In one direction, we can embed arbitrary circuits in the space with an essentially linear size increase. The other direction is by a communication complexity argument.