# Different definitions of Exponential Time Hypothesis

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

• Strong ETH states that $\delta_q \to 1$. Dec 5 '20 at 11:46
• 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. Dec 5 '20 at 11:47
• 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) Dec 5 '20 at 11:54
• Wikipedia mentions an explanation as well as a relevant citation. Have you consulted Flum & Grohe (2006)? Dec 5 '20 at 12:28