# Most general setting for fine-grained exponential-time complexity classes?

Consider the class of functions computable in time $(b+o(1))^n = 2^{\log_2{(b)} \times n + o(n)}$ on a $2$-tape Turing machine.

By the Hennie-Stearns theorem, the same functions are computable in time $(b+o(1))^n$ on a $k$-tape Turing machine for any $k \geq 2$. And we can extend this equivalence to any model of computation that has an essentially linear time translation to and from $2$-tape machines. But this isn't a very natural class, even given that we believe in the extended Church-Turing thesis.

If we account for the space usage as well, more models are time-translatable with a blowup of the form $O(t \times s^k)$. For example, when emulating a $2$-tape machine on a $1$-tape machine, it only has to scan the space used each time step, so the time blowup is $O(t \times s)$. Similarly, it seems like for RAM models there is a small $k$ that works: use one tape as an associative memory, a list of key-value pairs, which the emulator searches to find a key written on a different tape.

Now it seems sensible to say something like this: $F$ is computable in $(b+o(1))^n$ time and $2^{o(n)} = (1+o(1))^n$ space. I don't have to say what model I'm using because all the obvious ones work. There is sort of a trade-off here, in exchange for a subexponential space restriction, we can specify a particular base $b$ for the time complexity of our function that's invariant in a larger context.

That's about as far as I understand this issue right now. And I could be completely mistaken about something so partly I'm looking for some reassurance that the above is roughly correct. But I wonder if that's all there is to it? Is there some other set of assumptions under which the exponential time base of a function can be uniquely specified?

EXAMPLE: Rubinstein's theorem says that we can factor with base $2^\frac{1}{3}$. Since the algorithm uses subexponential space, this result is robust across models.

EXAMPLE: The square-root barrier for finding primes. If it were broken by exhibiting an algorithm that required exponential space on a Turing machine, would that really be a natural result, or possibly just an artifact of the machine model?

EXAMPLE: The Strong Exponential-Time Hypothesis. Might it be the case that a RAM program can solve general $\text{CNF-SAT}$ in exponential time with a base less than $2$, but also requiring exponential space, so that when translated to a TM the algorithm runs in exponential time with a base at least $2$ and (a slightly-weakened version of) SETH is true in the TM model only? Is there a variant of SETH where only subexponential space algorithms are considered in order to make it applicable to more models? Or is there some reason I'm not understanding that no generality is lost without this assumption?

• SETH doesn't talk about 3SAT. You might want to change that part. – ivmihajlin Dec 6 '17 at 1:27

## 1 Answer

Your description looks correct. The equivalence between deterministic models (under essentially linear time translation) for algorithms using $t^{o(1)}$ space (if the input size is $t^{o(1)}$ or we have random access to the input) is a nice observation. (However, we do know yet know whether randomized algorithms might be faster (even for $t^{o(1)}$ input size), and quantum algorithms are likely to be faster and might even violate extended Church-Turing thesis.)

Two other cases of essentially linear translation:

• Different reasonable parallel models with $t^{1+o(1)}$ size and $t^{o(1)}$ depth appear equivalent (in the sense that the translation still has $t^{1+o(1)}$ size and $t^{o(1)}$ depth) and can be simulated on a TM in $t^{1+o(1)}$ time.

• Nondeterministic time, since a nondeterministic Turing machine can guess and verify history of a nondeterministic RAM machine.

The square-root barrier for finding primes is likely a number theory problem rather than a computational problem. The naive algorithm (with a polynomial time primality test) for finding the least prime above $x$ is conjectured to be polynomial time (in $\log x$). A provable deterministic algorithm finding a decimal $k$-digit prime in time $O(10^{k/2-ε})$ using RAM but not TM could potentially come from some memory-intensive partial derandomization that does not answer the question of $O(n^{1/2-ε})$ upper bound between consecutive primes.

For SETH, the convention is to use RAM machines. Otherwise, its key application, the fine-grained complexity lower-bounds, would not work for RAM machines. It appears open whether any of the implications SETH ⇒ "SETH for TM" ⇒ "SETH for $2^{o(n)}$ space" can be reversed.

Also, under SETH, for a number of problems, the best exponent is the same for TM and RAM. For example, for minimum edit distance, the essentially quadratic time algorithm can be made to work for TM while the i.o. essentially quadratic lower bound works even for RAM.

• Thanks Dmytro, this is a helpful answer. What I am still trying to understand, and maybe I need to ask another follow-up question, is why we define fine-grained time-complexity the way we do, in terms of a specific model. For this to be a natural definition (invariant across models), we need an unproven and seemingly dubious assumption (that all models have an essentially linear time translation)... – Dan Brumleve Dec 5 '17 at 21:38
• However, we can define DTIME an entirely different way that is also model-invariant by assuming an entirely different unproven assumption, that all exponential-time algorithms can also be made subexponential-space (cstheory.stackexchange.com/questions/39653/…) and ignoring whether or not essentially linear time translations exist. So I am still wondering why we don't do it that way instead? All I can think of is that it is less effective (we don't know the exponent for edit distance for example). – Dan Brumleve Dec 5 '17 at 21:40
• @DanBrumleve In most cases, RAM based models are a reasonable approximation to modern (nonparallel) computers; and we have to choose a model to state the complexity of an algorithm and to compare quoted results from different papers, even though the model is arguably arbitrary. (Also, we do not expect that all exponential time algorithms can be made subexponential space.) – Dmytro Taranovsky Dec 5 '17 at 22:20
• I asked my follow-up question on math.SE: math.stackexchange.com/questions/2556780/…. Thanks again Dmytro for your informative answers. – Dan Brumleve Dec 9 '17 at 3:48