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

Question

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?

Answer 1

(Just now noticed this question.) There are a lot of questions in the above question. I will try to just address the last few.

Might it be the case that a RAM program can solve general 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?

SETH is generally stated in the word RAM model (in particular, with $O(\log t)$ word size, where the running time is $t$). This is mainly because most (if not all?) algorithmists don't care about or work in the multi-tape Turing machine model, but rather a random-access style model. It is true that in general we do not know how to simulate such time-t RAMs with multi-tape Turing machines super-efficiently, and (more importantly) we do not know how to simulate such RAMs in less than $O(t^2)$ gates with a Boolean circuit. But see the answer to the next question.

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?

Note there is a very simple time-space tradeoff one can obtain, if SETH is false. Suppose we have a $2^{\beta n}$ time algorithm $A$ for k-SAT on $n$ variables, using $\Theta(2^{\beta n})$ space, where $\beta < 1$. Consider the following algorithm $A_{\alpha}$ parameterized by some parameter $\alpha \in (0,1)$:

On $k$-SAT formula $F$, enumerate all assignments $a$ to the first $n-\alpha n$ variables of $F$, plug $a$ into $F$ and run $A$ on the resulting $\alpha n$-variable formula. Stop and output a SAT assignment if it's found.

Note the above $A_{\alpha}$ runs in $O(2^{n-\alpha n}\cdot 2^{\beta \alpha n}) \leq O(2^{n-(1-\beta)\alpha n})$ time and uses only $\Theta(2^{\beta \alpha n}+\alpha n)$ space.

Corollary: If $k$-SAT has a $2^{\beta n}$ time algorithm, then for every $\epsilon \in (0,\beta)$ there is a $\delta > 0$ such that $k$-SAT can be solved in $O(2^{\epsilon n})$ space and $O(2^{(1-\delta)n})$ time.

Proof: Let $k$-SAT have a $2^{\beta n}$ time algorithm. For any given $\epsilon \in (0,\beta)$, set $\alpha = \epsilon/\beta < 1$. Applying the above reduction, we can solve $k$-SAT in $O(2^{\epsilon n})$ space and $2^{n-(1-\beta)\alpha n}$ time, so $\delta = (1-\beta)\alpha$ suffices. QED

However, note the time-space product of the resulting algorithm is not very favorable...

I do think that the "polynomial-space SETH" (which I believe I have seen in the literature, but am blanking on a reference) that only rules out polynomial-space faster-than-$2^n$ time for $k$-SAT, is a much more plausible hypothesis than SETH itself.

Answer 2

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.