<p>First part:</p>
<p><span class="math-container">$2^{h(\delta)n}+2^{\epsilon n}+2^{\epsilon n}2^{(s_k+ \epsilon)(1-(\delta/ek))n} \leq 2^{(s_\infty(1-d/k)+2\epsilon)n}$</span></p>
<p><span class="math-container">$\implies2^{(s_\infty/2)n} + 2^{(s_k+ \epsilon)(1-(\delta/ek))n +\epsilon n} \leq 2^{(s_\infty(1-d/k)+2\epsilon)n}$</span></p>
<p><span class="math-container">$\implies  2^{(s_k+ \epsilon)(1-(\delta/ek))n +\epsilon n} \leq 2^{(s_\infty(1-d/k)+2\epsilon)n}-2^{(s_\infty/2)n}\approx 2^{(s_\infty(1-d/k)+2\epsilon)n}$</span></p>
<p><span class="math-container">$\implies 2^{(s_k+ \epsilon)}\leq 2^{(s_\infty(1-d/k)}
(\because (1-(\delta/ek)) \approx 1 \space \text {and} \space \epsilon \space \text {is arbitrarily small})$</span></p>
<p><span class="math-container">$\implies s_k \leq s_\infty(1-d/k)$</span></p>
<p>Second part:</p>
<p>Since in that paper mentioned, <span class="math-container">$d \approx s_{\infty}/(2e\log(2/s_{\infty}))$</span> and we are given from first part <span class="math-container">$s_k \leq s_\infty(1-d/k)$</span>, how to get <span class="math-container">$s_k \leq (1 − \Omega(k^{−1}))s_{\infty}$</span>? Need anybody's help.</p>

CC BY-SA 4.0
2024-02-10T09:01:48.047Z
I really have no idea what goes in your mind wrt the second part. Since $d$ is a *constant*, $s_k\le s_\infty(1-d/k)$ means $s_k\le s_\infty(1-\Omega(k^{-1}))$ directly from the definition of $\Omega$, there is nothing to prove here.
Emil Jeřábek
CC BY-SA 4.0
2024-02-09T22:30:42.153Z
2024-02-10T08:56:03.767Z
2024-02-10T08:56:03.767Z
S. M.
<p>I followed from this <a href="https://cstheory.stackexchange.com/questions/53820/sparsification-and-critical-clauses-in-sat">question</a>.</p>
<p>I need to prove, the final result <span class="math-container">$s_k \leq (1 − \Omega(k^{−1}))s_{\infty}.$</span></p>
<p>But before prove the final result first I need to prove the <span class="math-container">$s_k \leq (1 − d/k))s_{\infty}$</span>.
This prove existed in the paper, <a href="https://drive.google.com/file/d/1iI6byUc6azTMOgRiCXIoE5sAK4J_rRop/view?usp=drivesdk" rel="nofollow noreferrer">On the Complexity of k-SAT</a> by
Russell Impagliazzo and Ramamohan Paturi, 374 page, Theorem 3.</p>
<p>In that paper, one calculation I am not able to understand, which is,</p>
<p><span class="math-container">$2^{h(\delta)n}+2^{\epsilon n}+2^{\epsilon n}2^{(s_k+ \epsilon)(1-(\delta/ek))n} \leq 2^{(s_\infty(1-d/k)+2\epsilon)n}$</span></p>
<p>,where <span class="math-container">$h(\delta) \leq s_\infty/2$</span> ,
<span class="math-container">$d \approx s_{\infty}/(2e\log(2/s_{\infty}))$</span> and, <span class="math-container">$\epsilon$</span> is  arbitrarily small.</p>
<p>My question is how to get <span class="math-container">$s_k \leq (1 − d/k))s_{\infty}$</span> from the above inequality? If I plug the  value of <span class="math-container">$h(\delta)$</span> and ignore the <span class="math-container">$\epsilon$</span> related terms, also unable to deduce <span class="math-container">$s_k \leq (1 − d/k))s_{\infty}$</span>.</p>
<p>And my second question is that how to get final result <span class="math-container">$s_k \leq (1 − \Omega(k^{−1}))s_{\infty}$</span> from <span class="math-container">$s_k \leq (1 − d/k))s_{\infty}$</span>?</p>

CC BY-SA 4.0
2024-02-06T10:08:32.900Z
Simultaneously cross-posted at https://mathoverflow.net/questions/463578/complexity-analysis-on-sparsification-and-critical-clauses-in-sat . You were told many times before this is against the site rules.
Emil Jeřábek
CC BY-SA 4.0
2024-02-10T08:57:49.197Z
I'm sorry, but I'm not your personal tutor, and these basic calculations are not appropriate for this site, which is for *research-level* questions. You should post such questions at https://math.stackexchange.com or https://cs.stackexchange.com .
Emil Jeřábek
<reference-request><time-complexity><sat><exp-time-algorithms>
Calculation on Sparsification and critical clauses in SAT
S. M.
# Calculation on Sparsification and critical clauses in SAT

(Asked by: username_0 on 2024-02-05)

I followed from this [question](https://cstheory.stackexchange.com/questions/53820/sparsification-and-critical-clauses-in-sat).

I need to prove, the final result $s\_k \leq (1 − \Omega(k^{−1}))s\_{\infty}.$

But before prove the final result first I need to prove the $s\_k \leq (1 − d/k))s\_{\infty}$.
This prove existed in the paper, [On the Complexity of k-SAT](https://drive.google.com/file/d/1iI6byUc6azTMOgRiCXIoE5sAK4J_rRop/view?usp=drivesdk) by
Russell Impagliazzo and Ramamohan Paturi, 374 page, Theorem 3.

In that paper, one calculation I am not able to understand, which is,

$2^{h(\delta)n}+2^{\epsilon n}+2^{\epsilon n}2^{(s\_k+ \epsilon)(1-(\delta/ek))n} \leq 2^{(s\_\infty(1-d/k)+2\epsilon)n}$

,where $h(\delta) \leq s\_\infty/2$ ,
$d \approx s\_{\infty}/(2e\log(2/s\_{\infty}))$ and, $\epsilon$ is arbitrarily small.

My question is how to get $s\_k \leq (1 − d/k))s\_{\infty}$ from the above inequality? If I plug the value of $h(\delta)$ and ignore the $\epsilon$ related terms, also unable to deduce $s\_k \leq (1 − d/k))s\_{\infty}$.

And my second question is that how to get final result $s\_k \leq (1 − \Omega(k^{−1}))s\_{\infty}$ from $s\_k \leq (1 − d/k))s\_{\infty}$?

**Tags:** reference-request, time-complexity, sat, exp-time-algorithms
> **Comments:**
> **username_1**: Simultaneously cross-posted at https://mathoverflow.net/questions/463578/complexity-analysis-on-sparsification-and-critical-clauses-in-sat . You were told many times before this is against the site rules.  
> **username_1**: I'm sorry, but I'm not your personal tutor, and these basic calculations are not appropriate for this site, which is for *research-level* questions. You should post such questions at https://math.stackexchange.com or https://cs.stackexchange.com .  

---

## 1 answers

### Answer by username_0 on 2024-02-09. Score: 1 | Accepted answer

First part:

$2^{h(\delta)n}+2^{\epsilon n}+2^{\epsilon n}2^{(s\_k+ \epsilon)(1-(\delta/ek))n} \leq 2^{(s\_\infty(1-d/k)+2\epsilon)n}$

$\implies2^{(s\_\infty/2)n} + 2^{(s\_k+ \epsilon)(1-(\delta/ek))n +\epsilon n} \leq 2^{(s\_\infty(1-d/k)+2\epsilon)n}$

$\implies 2^{(s\_k+ \epsilon)(1-(\delta/ek))n +\epsilon n} \leq 2^{(s\_\infty(1-d/k)+2\epsilon)n}-2^{(s\_\infty/2)n}\approx 2^{(s\_\infty(1-d/k)+2\epsilon)n}$

$\implies 2^{(s\_k+ \epsilon)}\leq 2^{(s\_\infty(1-d/k)}
(\because (1-(\delta/ek)) \approx 1 \space \text {and} \space \epsilon \space \text {is arbitrarily small})$

$\implies s\_k \leq s\_\infty(1-d/k)$

Second part:

Since in that paper mentioned, $d \approx s\_{\infty}/(2e\log(2/s\_{\infty}))$ and we are given from first part $s\_k \leq s\_\infty(1-d/k)$, how to get $s\_k \leq (1 − \Omega(k^{−1}))s\_{\infty}$? Need anybody's help.

> **Comments:**
> **username_1**: I really have no idea what goes in your mind wrt the second part. Since $d$ is a *constant*, $s_k\le s_\infty(1-d/k)$ means $s_k\le s_\infty(1-\Omega(k^{-1}))$ directly from the definition of $\Omega$, there is nothing to prove here.  

---

