12
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
18
$\begingroup$

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."

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.

Improve this answer
$\endgroup$
5
  • 3
    $\begingroup$ Thank you! You definitely answered my question, but doesn't SETH say that $\delta=1$? $\endgroup$
    – Alex Golovnev
    Dec 2, 2013 at 9:25
  • 2
    $\begingroup$ Not quite. I fixed the quantifiers. $\endgroup$
    – Ryan Williams
    Dec 4, 2013 at 18:44
  • $\begingroup$ 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? $\endgroup$
    – Martin Schwarz
    Feb 22, 2015 at 13:57
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ryan Williams
    Feb 22, 2015 at 20:14
  • $\begingroup$ 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. $\endgroup$
    – Martin Schwarz
    Feb 24, 2015 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.