<p>SETH says that for all $\delta &lt; 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. </p>

<p>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 <em>not</em> 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 <em>can</em> 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, <a href="http://scholar.google.com/scholar?q=On%20the%20Difference%20Between%20Turing%20Machine%20Time%20and%20Random-Access%20Machine%20Time.">"On the Difference Between Turing Machine Time and Random-Access Machine Time."</a> </p>

<p>To address your specific questions: no, a multitape Turing machine is not automatically implied here, but yes, such an "algorithm" for SAT (under the usual random-access model) would break SETH.</p>

CC BY-SA 3.0
2013-12-02T09:25:14.803Z
Thank you! You definitely answered my question, but doesn't SETH say that $\delta=1$?
Alex Golovnev
CC BY-SA 3.0
2013-12-04T18:44:58.317Z
Not quite. I fixed the quantifiers.
Ryan Williams
CC BY-SA 3.0
2015-02-22T13:57:47.327Z
What about the quantum computers in this context? Aren't there any consequences of Grover's algorithm in this context? Is there any work on assuming a quantum analogue of the ETH?
Martin Schwarz
CC BY-SA 3.0
2015-02-22T20:14:24.577Z
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.
Ryan Williams
CC BY-SA 3.0
2015-02-24T14:24:58.423Z
Sure, but don't these better-than-classical speed-up and the "quatum SETH" have already any implications at some other place in complexity theory? Just wondering.
Martin Schwarz
CC BY-SA 3.0
2013-12-01T06:21:54.123Z
2013-12-04T18:44:12.763Z
2013-12-04T18:44:12.763Z
Ryan Williams
<p><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.129.7944&amp;rep=rep1&amp;type=pdf">Impagliazzo, Paturi</a> and <a href="http://faculty.cs.tamu.edu/chen/iwpec2009/images/52.pdf">Calabro, Impagliazzo, Paturi</a> 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$.  </p>

<p>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., <a href="http://arxiv.org/pdf/1112.2275.pdf">Cygan, Dell, Lokshtanov, Marx, Nederlof, Okamoto, Paturi, Saurabh, Wahlstrom</a>) don't need to make assumptions about the underlying model of computation. </p>

<p>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?</p>

<cc.complexity-theory><sat><exp-time-algorithms>
Computational Model in SETH
Alex Golovnev
# Computational Model in SETH

(Asked by: username_0 on 2013-11-30)

[Impagliazzo, Paturi](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.129.7944&rep=rep1&type=pdf) and [Calabro, Impagliazzo, Paturi](http://faculty.cs.tamu.edu/chen/iwpec2009/images/52.pdf) 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](http://arxiv.org/pdf/1112.2275.pdf)) 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?

**Tags:** cc.complexity-theory, sat, exp-time-algorithms


---

## 1 answers

### Answer by username_1 on 2013-12-01. Score: 18 | Accepted answer

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."](http://scholar.google.com/scholar?q=On%20the%20Difference%20Between%20Turing%20Machine%20Time%20and%20Random-Access%20Machine%20Time.)

To address your specific questions: no, a multitape Turing machine is not automatically implied here, but yes, such an "algorithm" for SAT (under the usual random-access model) would break SETH.

> **Comments:**
> **username_0**: Thank you! You definitely answered my question, but doesn't SETH say that $\delta=1$?  
> **username_1**: Not quite. I fixed the quantifiers.  
> **username_2**: What about the quantum computers in this context? Aren't there any consequences of Grover's algorithm in this context? Is there any work on assuming a quantum analogue of the ETH?  
> **username_1**: 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.  
> **username_2**: Sure, but don't these better-than-classical speed-up and the "quatum SETH" have already any implications at some other place in complexity theory? Just wondering.  

---

