1
$\begingroup$

I am reading basics of Exponential Time Hypothesis (ETH). There are two statements for it:

Statement 1
There exists no $2^{o(n)}$ algorithm for $3$-SAT, where $n$ is the number of variables.

Statement 2
If $\delta_q$ ($q \ge 3$) is the infimum of set of constants $c$ for which there exists an algorithm for solving $q$-SAT (each clause has $\le q$ literals) in time $\mathcal{O}^{\text{*}}(2^{cn})$ (here $\mathcal{O}^{\text{*}}(.)$ supresses any non-exponential part of the running time). Then $\delta_q > 0$.

I can see that if $1$ holds, then so does $2$. But why is it so that $2$ may/may not imply $1$ ? If $2$ holds then would it be wrong to argue that $\delta_3 > 0$. And as $\delta_{i+1} \ge\delta_i$ ($i \ge 3$), because increasing upper bound on number of literals in each clause can only make the problem more difficult to solve, it will imply $1$.

$\endgroup$
4
  • $\begingroup$ Strong ETH states that $\delta_q \to 1$. $\endgroup$ Dec 5 '20 at 11:46
  • $\begingroup$ Also, the sequence $\delta_q$ is (possibly weakly) increasing. If you can solve $(k+1)$-SAT, then you can use the same algorithm to solve $k$-SAT using a single new dummy variable. $\endgroup$ Dec 5 '20 at 11:47
  • $\begingroup$ Sorry for the confusion, I changed the wording. The two statements for ETH are mentioned here en.wikipedia.org/wiki/Exponential_time_hypothesis (have added same link in question as well) $\endgroup$
    – sashas
    Dec 5 '20 at 11:54
  • 1
    $\begingroup$ Wikipedia mentions an explanation as well as a relevant citation. Have you consulted Flum & Grohe (2006)? $\endgroup$ Dec 5 '20 at 12:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.