<p>This is an answer to the updated question (the original question seems harder).</p>
<p>Let <span class="math-container">$\mu'_k$</span> be the smallest constant such that <span class="math-container">$k$</span>-SAT that has clauses of length exactly <span class="math-container">$k$</span> and no trivial clauses has a <span class="math-container">$O(2^{\mu'_k m})$</span> time algorithm.
Let <span class="math-container">$\mu_k$</span> be the smallest constant such that <span class="math-container">$k$</span>-SAT with any clauses of length at most <span class="math-container">$k$</span> has an <span class="math-container">$O(2^{\mu_k m})$</span> time algorithm. I will prove that <span class="math-container">$\mu'_k = \mu_k$</span>.</p>
<p>Proof: Clearly we have <span class="math-container">$\mu'_k \le \mu_k$</span>. To prove that <span class="math-container">$\mu_k \le \mu'_k$</span> suppose we have an algorithm for <span class="math-container">$k$</span>-SAT with nontrivial clauses of length exactly <span class="math-container">$k$</span> with time complexity <span class="math-container">$O(2^{\mu'_k m})$</span>. To solve general <span class="math-container">$k$</span>-SAT with <span class="math-container">$m$</span> clauses, we add <span class="math-container">$k$</span> extra variables to the input formula and <span class="math-container">$2^k-1$</span> extra clauses over these new variables to forbid all assignments except the all-false assignment. Now, these <span class="math-container">$k$</span> extra variables can be freely added to any clauses of length less than <span class="math-container">$k$</span> to make them length exactly <span class="math-container">$k$</span>. Now we have a restricted instance with <span class="math-container">$m + 2^k-1$</span> clauses, and solve it in <span class="math-container">$O(2^{\mu'_k (m + 2^k-1)})$</span> time, which for constant <span class="math-container">$k$</span> is <span class="math-container">$O(2^{\mu'_k m})$</span> time.<span class="math-container">$\square$</span></p>
<p>It is easy to see that for <span class="math-container">$a \le b$</span> it holds that <span class="math-container">$\mu_a \le \mu_b$</span>, and it is well-known (e.g. in section 14.1 of the book Parameterized Algorithms) that assuming ETH, <span class="math-container">$\mu_3 &gt; 0$</span>. Therefore showing that <span class="math-container">$\mu'_k \rightarrow 0$</span> as <span class="math-container">$k \rightarrow \infty$</span> would break ETH.</p>

CC BY-SA 4.0
2020-11-27T10:05:31.727Z
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...
Giorgio Camerani
CC BY-SA 4.0
2020-11-27T10:14:44.720Z
...$\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.
Giorgio Camerani
CC BY-SA 4.0
2020-11-27T10:37:45.983Z
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.
Laakeri
CC BY-SA 4.0
2020-11-27T12:31:37.507Z
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 https://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}$.
Giorgio Camerani
CC BY-SA 4.0
2020-11-29T20:43:37.167Z
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...
daniello
CC BY-SA 4.0
2020-11-27T08:50:25.070Z
2020-11-27T08:50:25.070Z
Laakeri
<p>It has been shown in <a href="https://cseweb.ucsd.edu/%7Erussell/ipz.pdf" rel="nofollow noreferrer">[1]</a> that <span class="math-container">$k\text{-SAT}$</span> has a <span class="math-container">$2^{o(n)}$</span> algorithm if and only if it has a <span class="math-container">$2^{o(m)}$</span> algorithm, <span class="math-container">$n$</span> being the number of variables and <span class="math-container">$m$</span> being the number of clauses.</p>
<p>Being <span class="math-container">$s_k=\text{inf}\{\delta: \text{there exists }2^{\delta n}\text{ algorithm for solving }k\text{-SAT}\}$</span>, it has been shown in <a href="https://cseweb.ucsd.edu/%7Epaturi/myPapers/pubs/ImpagliazzoPaturi_2001_jcss.pdf" rel="nofollow noreferrer">[2]</a> that, assuming <span class="math-container">$\text{ETH}$</span>, <span class="math-container">$s_k$</span> increases infinitely often as <span class="math-container">$k\to \infty$</span>, that is to say the complexity of <span class="math-container">$k\text{-SAT}$</span> grows as <span class="math-container">$k$</span> grows.</p>
<blockquote>
<p><strong>Question</strong><br />
Is the second statement known to hold, under <span class="math-container">$\text{ETH}$</span>, also in the <span class="math-container">$2^{o(m)}$</span> realm?<br />
More precisely, being <span class="math-container">$\mu_k=\text{inf}\{\delta: \text{there exists }2^{\delta m}\text{ algorithm for solving }k\text{-SAT}\}$</span>, does <span class="math-container">$\text{ETH}$</span> imply that <span class="math-container">$\mu_k$</span> increases infinitely often as <span class="math-container">$k \to \infty$</span>?</p>
</blockquote>
<hr/>
<ol>
<li><a href="https://cseweb.ucsd.edu/%7Erussell/ipz.pdf" rel="nofollow noreferrer">Which Problems Have Strongly Exponential Complexity?</a> by R. Impagliazzo, R. Paturi and F. Zane (December 1999)</li>
<li><a href="https://cseweb.ucsd.edu/%7Epaturi/myPapers/pubs/ImpagliazzoPaturi_2001_jcss.pdf" rel="nofollow noreferrer">On the Complexity of <span class="math-container">$k$</span>-SAT</a> by R. Impagliazzo and R. Paturi (January 2001)</li>
</ol>
<p><strong>Update 22/11/2020</strong><br />
To avoid ambiguities or misunderstandings, let me clarify that here the number of clauses is not super-linear in the number of variables. The <span class="math-container">$k\text{-SAT}$</span> instance I'm talking about is already sparse, that is to say <span class="math-container">$m = \Theta(n)$</span>. I'm interested in knowing the consequences on <span class="math-container">$\text{ETH}$</span>, if any, of an algorithm running in time <span class="math-container">$2^{\delta m}$</span> where <span class="math-container">$\delta \to 0$</span> as <span class="math-container">$k \to \infty$</span>. The existence of such algorithm proves that the sequence <span class="math-container">$\mu_k$</span> as defined above decreases monotonically, rather than increasing infinitely often. That's precisely why I've asked this question in the first place.</p>
<p><strong>Update 26/11/2020</strong><br />
Following daniello's comment below, let me clarify that here each clause has <em>exactly</em> <span class="math-container">$k$</span> <em>distinct</em> literals, and that trivial clauses are not allowed to be present.</p>

CC BY-SA 4.0
2020-11-20T19:13:55.863Z
Neat question!  The first part of what you said is stated as Proposition 2.9 in "Lower bounds based on the Exponential Time Hypothesis" (https://www.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.
Michael Wehar
CC BY-SA 4.0
2020-11-22T19:04:15.760Z
@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.
Giorgio Camerani
CC BY-SA 4.0
2020-11-24T07:12:46.707Z
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)
daniello
CC BY-SA 4.0
2020-11-26T09:10:56.887Z
@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.
Giorgio Camerani
CC BY-SA 4.0
2020-11-26T15:08:21.030Z
The papers [1] and [2] are about the setting where a $k$CNF can have clauses of any size at most $k$ (i.e. the "$\leq k$" case).
Kristoffer Arnsfelt Hansen
CC BY-SA 4.0
2020-11-26T19:38:53.280Z
@KristofferArnsfeltHansen Yes of course, and as such they clearly encompass the $=k\text{-SAT}$ instances I'm interested in. This is how I personally understand it: those papers have been forged around the choice of adopting the $\leq k$ definition, because they have silently assumed that _any_ conceivable algorithm having a certain performance on $=k\text{-SAT}$ must have a _better_ performance on $=k'\text{-SAT}$ for every $k' < k$. It is just that such assumption happens to be false _in general_.
Giorgio Camerani
CC BY-SA 4.0
2020-11-26T19:53:06.537Z
Can't we just pad the instance with $k$ extra variables and $2^k-1$ extra clauses to force them all to be false, and then use these to pad clauses with length $<k$ into equivalent clauses of length $k$? In particular, by this argument for constant $k$ there is only an additive constant of difference in the exactly $k$ length and at most $k$ length cases.
Laakeri
CC BY-SA 4.0
2020-11-26T20:24:37.853Z
So it seems to follow that assuming ETH, there is no algorithm with $\delta \rightarrow 0$ as $k \rightarrow \infty$. However, I don't know if this implies anything to the question of whether $\mu_k$ increases infinitely often or whether $\mu_k = \mu_3$ (I suspect that one of these cases hold).
Laakeri
CC BY-SA 4.0
2020-11-26T21:13:56.507Z
@Laakeri [about your before last comment] Yes correct, with just $2$ observations: 1) those $k$ variables need not to be extra, they can be any subset of the original $n$ variables; 2) the extra clauses to be used to pad the original $m$ clauses need to be $2^k$ (with that $-1$ it is not going to work).
Giorgio Camerani
CC BY-SA 4.0
2020-11-26T21:27:54.833Z
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.
Laakeri
CC BY-SA 4.0
2020-11-26T21:39:28.437Z
@Laakeri Let $c$ be a clause of the original instance, with $|c|=k'$ where $k' < k$. Pick any subset of $k - k'$ variables from the original $n$ variables (taking care that none of the picked variables is already mentioned in $c$). Remove $c$ and replace it with a block $b_c$ of $2^{k-k'}$ new clauses, where the first $k'$ literals are the literals of $c$, and the remaining $k-k'$ literals are $1$ of the $2^{k-k'}$ combinations of signs, $1$ different such combination for each clause in the block. Now repeat this same process for every clause $c_1, \cdots, c_m$ originally present...
Giorgio Camerani
CC BY-SA 4.0
2020-11-26T21:47:21.507Z
Your reduction multiplies the number of clauses by a value that depends on $k$, which is undesired in our context, as it changes the constant in the exponent. Note that my reduction only adds a number of clauses that depends on $k$, and thus it does affect the time complexity.
Laakeri
CC BY-SA 4.0
2020-11-26T21:49:00.780Z
...in the input formula. Now let $x$ be any boolean assignment to the $n$ variables: it can either be satisfying for the input formula, or not. Whatever such $x$ is, let's see the effect it has on the $m$ blocks $b_{c_1}, \cdots, b_{c_m}$: for each such block $b_c$, $x$ will satisfy exactly $2^k-1$ clauses in $b_c$ (i.e. all those such that _not all_ their $k-k'$ added literals appear negated in $x$), and will simplify $1$ of them to $c$. In the end the padded instance will simplify to the original instance, whatever $x$ is.
Giorgio Camerani
CC BY-SA 4.0
2020-11-26T22:10:49.440Z
@Laakeri I see that I have misinterpreted your reduction in the very first place. For some reason I misparsed your text _"...there is only an additive constant of difference..."_ as turning $\Delta = \frac{m}{n}$ of the original instance into $\Delta' = \frac{m'}{n}$ with $\Delta' = \Delta + \text{constant}$ (which is what my reduction does). Obviously I now agree that your reduction is correct and much better for the purpose, due to its additive nature.
Giorgio Camerani
CC BY-SA 4.0
2020-11-26T23:04:28.860Z
@Laakeri [about your former comment above, on ETH] I have shown a 15 lines algorithm (http://gcamerani.altervista.org/subexp/) which, when given a random $=k\text{-SAT}$ instance with clause density $\Delta = \frac{m}{n} \in 2^{o(k)}$, counts the exact number of satisfying assignments in deterministic time $2^{\varepsilon n}$ where $\varepsilon \to 0$ as $k \to \infty$. When $k \in \omega(1)$ this even translates into a sub-exponential time algorithm. More precisely $\varepsilon = \frac{\log(\Delta k)}{k}$, that's why it is powerless when $\Delta = 2^{\Theta(k)}$. See how with...
Giorgio Camerani
CC BY-SA 4.0
2020-11-26T23:45:09.337Z
...$\Delta = 2^{\xi k}$ for any constant $\xi < 1$, we are already below $2$, that is to say $C^n$ with $C < 2$ _independent_ of $k$: while the running time does no longer decrease as $k$ grows, it does not increase either. If a 15 lines algorithm was able to do all of this, I really struggle to believe that there _must not_ exist any conceivable algorithm (among the infinitely many existing), not even an ultra-smart and creative one with thousands of lines and using some yet unknown identity, able to circumvent both the random restriction and the $\Delta \in 2^{o(k)}$ restriction.
Giorgio Camerani
<cc.complexity-theory><ds.algorithms><sat><parameterized-complexity><exp-time-algorithms>
On $\text{ETH}$ with $m$ as parameter: consequences of algorithm running in time $2^{\delta m}$ where $\delta \to 0$ as $k \to \infty$
Giorgio Camerani
# On $\text{ETH}$ with $m$ as parameter: consequences of algorithm running in time $2^{\delta m}$ where $\delta \to 0$ as $k \to \infty$

(Asked by: username_0 on 2020-11-20)

It has been shown in [[1]](https://cseweb.ucsd.edu/%7Erussell/ipz.pdf) 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]](https://cseweb.ucsd.edu/%7Epaturi/myPapers/pubs/ImpagliazzoPaturi_2001_jcss.pdf) 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?](https://cseweb.ucsd.edu/%7Erussell/ipz.pdf) by R. Impagliazzo, R. Paturi and F. Zane (December 1999)
2. [On the Complexity of $k$-SAT](https://cseweb.ucsd.edu/%7Epaturi/myPapers/pubs/ImpagliazzoPaturi_2001_jcss.pdf) 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 username_2'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.

**Tags:** cc.complexity-theory, ds.algorithms, sat, parameterized-complexity, exp-time-algorithms

> **Comments:**
> **username_1**: Neat question!  The first part of what you said is stated as Proposition 2.9 in "Lower bounds based on the Exponential Time Hypothesis" (https://www.ii.uib.no/~username_2/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.  
> **username_0**: @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.  
> **username_2**: 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)  
> **username_0**: @username_2 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.  
> **username_3**: The papers [1] and [2] are about the setting where a $k$CNF can have clauses of any size at most $k$ (i.e. the "$\leq k$" case).  
> **username_0**: @KristofferArnsfeltHansen Yes of course, and as such they clearly encompass the $=k\text{-SAT}$ instances I'm interested in. This is how I personally understand it: those papers have been forged around the choice of adopting the $\leq k$ definition, because they have silently assumed that _any_ conceivable algorithm having a certain performance on $=k\text{-SAT}$ must have a _better_ performance on $=k'\text{-SAT}$ for every $k' < k$. It is just that such assumption happens to be false _in general_.  
> **username_4**: Can't we just pad the instance with $k$ extra variables and $2^k-1$ extra clauses to force them all to be false, and then use these to pad clauses with length $<k$ into equivalent clauses of length $k$? In particular, by this argument for constant $k$ there is only an additive constant of difference in the exactly $k$ length and at most $k$ length cases.  
> **username_4**: So it seems to follow that assuming ETH, there is no algorithm with $\delta \rightarrow 0$ as $k \rightarrow \infty$. However, I don't know if this implies anything to the question of whether $\mu_k$ increases infinitely often or whether $\mu_k = \mu_3$ (I suspect that one of these cases hold).  
> **username_0**: @username_4 [about your before last comment] Yes correct, with just $2$ observations: 1) those $k$ variables need not to be extra, they can be any subset of the original $n$ variables; 2) the extra clauses to be used to pad the original $m$ clauses need to be $2^k$ (with that $-1$ it is not going to work).  
> **username_4**: 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.  
> **username_0**: @username_4 Let $c$ be a clause of the original instance, with $|c|=k'$ where $k' < k$. Pick any subset of $k - k'$ variables from the original $n$ variables (taking care that none of the picked variables is already mentioned in $c$). Remove $c$ and replace it with a block $b_c$ of $2^{k-k'}$ new clauses, where the first $k'$ literals are the literals of $c$, and the remaining $k-k'$ literals are $1$ of the $2^{k-k'}$ combinations of signs, $1$ different such combination for each clause in the block. Now repeat this same process for every clause $c_1, \cdots, c_m$ originally present...  
> **username_4**: Your reduction multiplies the number of clauses by a value that depends on $k$, which is undesired in our context, as it changes the constant in the exponent. Note that my reduction only adds a number of clauses that depends on $k$, and thus it does affect the time complexity.  
> **username_0**: ...in the input formula. Now let $x$ be any boolean assignment to the $n$ variables: it can either be satisfying for the input formula, or not. Whatever such $x$ is, let's see the effect it has on the $m$ blocks $b_{c_1}, \cdots, b_{c_m}$: for each such block $b_c$, $x$ will satisfy exactly $2^k-1$ clauses in $b_c$ (i.e. all those such that _not all_ their $k-k'$ added literals appear negated in $x$), and will simplify $1$ of them to $c$. In the end the padded instance will simplify to the original instance, whatever $x$ is.  
> **username_0**: @username_4 I see that I have misinterpreted your reduction in the very first place. For some reason I misparsed your text _"...there is only an additive constant of difference..."_ as turning $\Delta = \frac{m}{n}$ of the original instance into $\Delta' = \frac{m'}{n}$ with $\Delta' = \Delta + \text{constant}$ (which is what my reduction does). Obviously I now agree that your reduction is correct and much better for the purpose, due to its additive nature.  
> **username_0**: @username_4 [about your former comment above, on ETH] I have shown a 15 lines algorithm (http://gcamerani.altervista.org/subexp/) which, when given a random $=k\text{-SAT}$ instance with clause density $\Delta = \frac{m}{n} \in 2^{o(k)}$, counts the exact number of satisfying assignments in deterministic time $2^{\varepsilon n}$ where $\varepsilon \to 0$ as $k \to \infty$. When $k \in \omega(1)$ this even translates into a sub-exponential time algorithm. More precisely $\varepsilon = \frac{\log(\Delta k)}{k}$, that's why it is powerless when $\Delta = 2^{\Theta(k)}$. See how with...  
> **username_0**: ...$\Delta = 2^{\xi k}$ for any constant $\xi < 1$, we are already below $2$, that is to say $C^n$ with $C < 2$ _independent_ of $k$: while the running time does no longer decrease as $k$ grows, it does not increase either. If a 15 lines algorithm was able to do all of this, I really struggle to believe that there _must not_ exist any conceivable algorithm (among the infinitely many existing), not even an ultra-smart and creative one with thousands of lines and using some yet unknown identity, able to circumvent both the random restriction and the $\Delta \in 2^{o(k)}$ restriction.  

---

## 1 answers

### Answer by username_4 on 2020-11-27. Score: 4

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.

> **Comments:**
> **username_0**: 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 username_2'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...  
> **username_0**: ...$\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.  
> **username_4**: 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.  
> **username_0**: 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 https://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}$.  
> **username_2**: 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...  

---

