8
$\begingroup$

It has been shown in [1] that $k\text{-SAT}$ has a $2^{o(n)}$ algorithm if and only if it has a $2^{o(m)}$ algorithm, $n$ being the number of variables and $m$ being the number of clauses.

Being $s_k=\text{inf}\{\delta: \text{there exists }2^{\delta n}\text{ algorithm for solving }k\text{-SAT}\}$, it has been shown in [2] that, assuming $\text{ETH}$, $s_k$ increases infinitely often as $k\to \infty$, that is to say the complexity of $k\text{-SAT}$ grows as $k$ grows.

Question
Is the second statement known to hold, under $\text{ETH}$, also in the $2^{o(m)}$ realm?
More precisely, being $\mu_k=\text{inf}\{\delta: \text{there exists }2^{\delta m}\text{ algorithm for solving }k\text{-SAT}\}$, does $\text{ETH}$ imply that $\mu_k$ increases infinitely often as $k \to \infty$?


  1. Which Problems Have Strongly Exponential Complexity? by R. Impagliazzo, R. Paturi and F. Zane (December 1999)
  2. On the Complexity of $k$-SAT by R. Impagliazzo and R. Paturi (January 2001)

Update 22/11/2020
To avoid ambiguities or misunderstandings, let me clarify that here the number of clauses is not super-linear in the number of variables. The $k\text{-SAT}$ instance I'm talking about is already sparse, that is to say $m = \Theta(n)$. I'm interested in knowing the consequences on $\text{ETH}$, if any, of an algorithm running in time $2^{\delta m}$ where $\delta \to 0$ as $k \to \infty$. The existence of such algorithm proves that the sequence $\mu_k$ as defined above decreases monotonically, rather than increasing infinitely often. That's precisely why I've asked this question in the first place.

Update 26/11/2020
Following daniello's comment below, let me clarify that here each clause has exactly $k$ distinct literals, and that trivial clauses are not allowed to be present.

$\endgroup$
16
  • 2
    $\begingroup$ Neat question! The first part of what you said is stated as Proposition 2.9 in "Lower bounds based on the Exponential Time Hypothesis" (ii.uib.no/~daniello/papers/surveyETH.pdf). In particular, it states that assuming $ETH$, there is a constant $s'$ such that $3$-$SAT$ is not solvable in $O(2^{s' \cdot m})$ time. I just thought it would be good to mention this survey as well. $\endgroup$ Nov 20, 2020 at 19:13
  • 1
    $\begingroup$ @MichaelWehar Thanks! That survey is indeed very useful and well written, really nice to have all such main knowledge summarized in a single paper. By the way I've just updated the question to better clarify the original intent behind it. $\endgroup$ Nov 22, 2020 at 19:04
  • 1
    $\begingroup$ I think the answer to the question could depend on whether $k$-SAT means clauses of size $\leq k$ or precisely $ k$. In the $\leq k$ case the sequence is monotnonically non-decreasing, while it is quite likely to converge to $0$ as $k$ tends to infinity in the $= k$ case (no formal argument, just a gut feeling based on the $2^{O(k)}n$ satisfiability threshold) $\endgroup$
    – daniello
    Nov 24, 2020 at 7:12
  • $\begingroup$ @daniello Thanks for this precision, I'm going to update the question to clarify that each clause has exactly $k$ distinct literals. Personally, I tend to dislike the $\leq k$ definition, because anyone can emerge from his basement exhibiting a graph (monotone $2\text{-SAT}$) and legitimately claiming it is a $g_{64}\text{-SAT}$ instance. $\endgroup$ Nov 26, 2020 at 9:10
  • 1
    $\begingroup$ I don't follow the previous comment. To pad clauses with extra literals, we need to make sure that these literals are false. So assuming we don't know anything about the instance, these padding variables must be extra. $\endgroup$
    – Laakeri
    Nov 26, 2020 at 21:27

1 Answer 1

4
$\begingroup$

This is an answer to the updated question (the original question seems harder).

Let $\mu'_k$ be the smallest constant such that $k$-SAT that has clauses of length exactly $k$ and no trivial clauses has a $O(2^{\mu'_k m})$ time algorithm. Let $\mu_k$ be the smallest constant such that $k$-SAT with any clauses of length at most $k$ has an $O(2^{\mu_k m})$ time algorithm. I will prove that $\mu'_k = \mu_k$.

Proof: Clearly we have $\mu'_k \le \mu_k$. To prove that $\mu_k \le \mu'_k$ suppose we have an algorithm for $k$-SAT with nontrivial clauses of length exactly $k$ with time complexity $O(2^{\mu'_k m})$. To solve general $k$-SAT with $m$ clauses, we add $k$ extra variables to the input formula and $2^k-1$ extra clauses over these new variables to forbid all assignments except the all-false assignment. Now, these $k$ extra variables can be freely added to any clauses of length less than $k$ to make them length exactly $k$. Now we have a restricted instance with $m + 2^k-1$ clauses, and solve it in $O(2^{\mu'_k (m + 2^k-1)})$ time, which for constant $k$ is $O(2^{\mu'_k m})$ time.$\square$

It is easy to see that for $a \le b$ it holds that $\mu_a \le \mu_b$, and it is well-known (e.g. in section 14.1 of the book Parameterized Algorithms) that assuming ETH, $\mu_3 > 0$. Therefore showing that $\mu'_k \rightarrow 0$ as $k \rightarrow \infty$ would break ETH.

$\endgroup$
5
  • $\begingroup$ I'm puzzled. While I follow all your reasoning and do not find anything wrong in it, the last sentence does not compile in my head. Reason is the second half of daniello's comment. In the random setting, the clause density $\Delta = \frac{m}{n}$ is critical at $\Delta \in 2^{\Theta(k)}$, where the hardest instances are situated (almost vertical collapse from being satisfiable w.h.p. to being unsatisfiable w.h.p.). Now if you take the obvious naïve $2^n$ brute-force algorithm, and just plug $n = \frac{m}{\Delta}$, you get a $2^{\mu_{k}' m}$ algorithm where... $\endgroup$ Nov 27, 2020 at 10:05
  • $\begingroup$ ...$\mu_{k}' = \frac{1}{\Delta} = \frac{1}{2^{\Theta(k)}}$ approaches $0$ as $k \to \infty$, which is clearly not sufficient to break ETH. Sounds like $\mu_{k}'$ shall approach $0$ a tiny bit faster than $\frac{1}{\Delta}$. Even just a multiplicative constant $\xi < 1$ would be sufficient, because it would mean that $k\text{-SAT}$ is doable in $2^{\xi n}$, where $\xi$ is independent of $k$. It would imply that the coefficient in the exponent bangs at $\xi$ and stops there, not increasing infinitely often as $k$ grows, and this would be enough to refute ETH. $\endgroup$ Nov 27, 2020 at 10:14
  • $\begingroup$ What you say seems plausible in the random input setting, but it seems that for this problem the random input setting and the worst-case setting are very different. $\endgroup$
    – Laakeri
    Nov 27, 2020 at 10:37
  • $\begingroup$ Mmm... I'm not sure. In the worst-case scenario the situation of the critical density threshold in terms of $k$ seems even worse than in the random case, right? For instance in the paper cseweb.ucsd.edu/~ccalabro/cip.pdf (where there is no random assumption at all) they also prove that instances of density slightly more than exponential in $k$ (i.e. $2^{k \log k}$) are almost the hardest instances of $k\text{-SAT}$. $\endgroup$ Nov 27, 2020 at 12:31
  • $\begingroup$ Lesson learned... never underestimate the power of simple gadgeteering. So in the worst case setting there isn’t any essential difference between clauses of size $\leq k$ vs $=k$; this only makes the original question (does the sequence $\mu_k$ increase infinitely often) more interesting... $\endgroup$
    – daniello
    Nov 29, 2020 at 20:43

Your Answer

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

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