Let SAT$_v$ be the language of those instances of SAT that contain variables $[v] = \{0,1,\dots,v-1\}$, let $k$-SAT be the language of those instances of SAT in which every clause has at most $k$ literals, and let $k$-SAT$_v$ be their intersection. Let $s_k = \inf_M\{\delta \mid \exists c\forall v\;( M\text{ decides } k\text{-SAT$_v$ in }2^{v\delta-c})\text{ time}) \}$, where the infimum ranges over all algorithms (machines in some model of computing). Let $s_\infty = \lim_{k \to \infty} s_k$. For this to make sense, one has to assume that there is a reasonable bound on the size of the input in terms of the number of variables; otherwise one could repeat clauses to force $s_k$ and $s_\infty$ to be as large as desired. So assume clauses are not repeated.
Note that each $k$-CNF formula then has size at most $O(v^k)$, so the size of the input formula is not important when considering an exponent that is linear in $v$. It then follows that $s_3 \le s_4 \le \dots \le s_\infty$.
The Exponential Time Hypothesis (ETH) is the statement that $s_k > 0$ for some $k\ge 3$. The sequence $(s_k)$ increases infinitely often if ETH holds. The Strong ETH (SETH) is the statement that $s_\infty \ge 1$ or $s_\infty = 1$, depending on which reference one uses.
In contrast, each instance of SAT$_v$ contains up to $3^v$ distinct clauses (each variable can be positive, negative, or absent in each clause). Hence an input may have length $\Omega(2^{n\log 3})$ even if no clause is repeated, so this is a lower bound for the time to read the input, and then also for the overall time.
If we then let $s_\omega = \inf_M\{\delta \mid \exists c\forall v\;( M\text{ decides } \text{SAT$_v$ in }2^{v\delta-c})\text{ time}) \}$, it is clear that $s_\omega \ge \log 3 \gt 1.58$ just by considering the input sizes. Even if one requires an input formula to contain no clause that is subsumed by another, $s_\omega \ge 1.5$. By the trivial algorithm, it is also the case that $s_\omega \le 1+\log 3$.
Why is there a gap between $s_\infty$ and $s_\omega$, assuming SETH?
In some sense $s_\omega$ is just a different way to take the limit, so it seems puzzling that there should be a gap.
- Russell Impagliazzo and Ramamohan Paturi, On the Complexity of $k$-SAT, JCSS 62 367–375, 2001. doi:10.1006/jcss.2000.1727 (preprint)
- Evgeny Dantsin and Alexander Wolpert, On Moderately Exponential Time for SAT, SAT 2010, LNCS 6175 313–325. doi:10.1007/978-3-642-14186-7_27 (preprint)
- Chris Calabro, Russell Impagliazzo and Ramamohan Paturi, The Complexity of Satisfiability of Small Depth Circuits, IWPEC 2009, LNCS 5917 75–85. doi:10.1007/978-3-642-11269-0_6 (preprint)
- Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlström, On Problems as Hard as CNF-SAT, arXiv:1112.2275v3, 27 Mar 2014.
