2
$\begingroup$

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)$?

$\endgroup$

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ My confusion was only that typically one measures the complexity in relation to the input size (measured in constant length machine words), whereas ETH measures it with the number of variables, which is not asymptotically the same if we allow a variable to occur $\omega(1)$ times. The sparsification lemma does not help too, because one can have both $o(n)$ clauses and $o(n)$ variables in a formula. $\endgroup$
    – rus9384
    May 14, 2022 at 8:49
  • $\begingroup$ Yes the bound stated in the conjecture relates to the number of variables and not to the size of the input. But this is quite often the case. For example for hard problems on graphs, we are usually interested in the running time in relation to the number of vertices and not the size of the input. $\endgroup$ May 15, 2022 at 21:06
  • $\begingroup$ I suppose the $NP$-hardness still is required. Because as I said, it is possible to have a formula that is not $NP$-hard but requires $2^{\Theta(|V|)}$ running time. $\endgroup$
    – rus9384
    May 16, 2022 at 9:59
  • $\begingroup$ ETH is stronger than NP$\neq$P (it already implies it). The size of a formula is the sum of the sizes of its clauses, and size of a clause is the number of literals in it. Try to think of the bounds SETH implies for a clause using the size of the formula as the parameter. $\endgroup$ May 16, 2022 at 10:07
  • 1
    $\begingroup$ Wanted to show a counterexample, but, a complete CNF would not suit sparsification lemma. Now I am thinking if there is an implication on the number of literals from that lemma. In fact, assuming number of clauses and variables is both $\Theta(f(n))$, there either would be repetitive clauses, or the number of literals would be polynomial in the number of variables. I guess this answers my question. $\endgroup$
    – rus9384
    May 16, 2022 at 19:28
1
$\begingroup$

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.

$\endgroup$

Your Answer

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

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