# Computational Model in SETH

Impagliazzo, Paturi and Calabro, Impagliazzo, Paturi introduced Exponential-Time Hypothesis (ETH) and Strongly Exponential-Time Hypothesis (SETH). Roughly, SETH says that there is no algorithm which solves SAT in time $1.99^n$.

I was wondering what would that mean to break SETH. We definitely need to find an algorithm which solves SAT in fewer than $2^n$ steps, but I don't quite understand what computational model we should use. As far as I know, results based on SETH (see, e.g., Cygan, Dell, Lokshtanov, Marx, Nederlof, Okamoto, Paturi, Saurabh, Wahlstrom) don't need to make assumptions about the underlying model of computation.

Assume, for example, that we found an algorithm which solves SAT in time $1.5^n$ using space $1.5^n$. Does it automatically imply that we can find a Turing Machine which solves this problem in time $1.99^n$? Does it break SETH?

SETH says that for all $\delta < 1$ there is a $k$ such that $k$-SAT requires $2^{\delta n}$ time to be solved in the worst-case. The computational model is generally taken to be the random-access machine or pointer machine model, which allows for $O(\log N)$ time access to a storage of $N$ items, and is generally assumed to also be probabilistic with bounded error.
As far as I know, it is open whether $2^{\delta n}$ time algorithms on such a model can be translated into two-tape Turing machines running in $2^{\delta n} \cdot poly(n)$ time. Nevertheless, proving that such a translation is not possible would separate multitape Turing machines from random access machines, which would have several very intriguing implications. For one, it would prove that SAT is not solvable in quasi-linear time on multitape Turing machines (because, if SAT could be solved with such multitape machines, then random-access machines can be efficiently simulated with multitape Turing machines). Note that many computational primitives (such as sorting, circuit evaluation, simple dynamic programming) can be implemented efficiently on multitape Turing machines. One relevant reference for these issues is Regan, "On the Difference Between Turing Machine Time and Random-Access Machine Time."
• Thank you! You definitely answered my question, but doesn't SETH say that $\delta=1$? Dec 2, 2013 at 9:25
• Regarding quantum algorithms, Grover gives about $$2^{n/2}$$ time for CNF SAT. But one could pose a "quantum SETH" which asserts that this square-root speedup is best possible. Feb 22, 2015 at 20:14