Exponential Time Hypothesis and the input size vs number of variables

Question

According to Exponential Time Hypothesis there does not exist a deterministic algorithm to solve SAT over $V$ variables in time $o(2^V)$. However, let's say the number of literals $n = \omega(poly(V))$. The real input size in the worst case is $\Theta(n)$, therefore for an asymptotic analysis one can assume $n$ to be the input size. Such a formula can be bruteforced in time $o(2^n)$, but not in time $o(2^V)$.

In an extreme case one could have $V = O(\log n)$ which would produce a problem in $\mathsf P$ and, therefore, invalid for Exponential Time Hypothesis. Can one assume that a valid problem for Strong Exponential Time Hypothesis has $V=\Theta(poly(n))$ or even $V = \Theta(n)$?

Answer 1

ETH says that, for $s_k = \inf \alpha$ such that k-sat can be solved in $2^{\alpha n}$, it holds that $s_3 > 0$.

The strong exponential time hypothesis (SETH) says that $\lim\limits_{k \rightarrow \infty}s_k = 1$. I think you mean the latter in your description.

Answering your question: The conjecture presents a lower-bound for a problem, meaning that no algorithm (in simple terms) solves all instances of $SAT$ much better than $O(2^{|V|})$[1]. However, in your question, you provided an example where a specific algorithm has a larger running time than this lower-bound for a specific class of instances.

On one hand, larger running time only makes a lower-bound stronger (it contradicts nothing). On the other side, even if you show that for some class of instances (there are surely many of them), the problem can be solved efficiently, this does not contradict the lower-bound since it is general and your algorithm has to solve SAT more efficiently on any given instance.

On a side note, the sparsification lemma [Impagliazzo et al.], used to show that SETH is stronger than ETH reduces an instance of SAT to many instances such that in each of them we have linear number of clauses in the number of variables. This might satisfy your curiosity since it shows that SETH also has implications on instances with linear bound on the number of clauses.

Some examples of classes of formulas that can be solved efficiently are CNF formulas whose primal-, dual- or incidence-graphs have bounded values of some width parameters (tree width / branch width / etc.)

---

[1]: This is equivalent to the CNF-SAT conjecture. SETH is a stronger hypothesis.

Answer 2

In their paper Impagliazzo and Paturi in Theorem 1 claim that ETH is equivalent to $\mathsf{SNP \not \subseteq SUBEXP}$.

Since complexity classes are defined on the input size and a formula on $o(n)$ variables is solvable in subexponential time, it follows that the number of variables has to be linear in the number of literals for ETH.