<p>The partial answer 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>

CC BY-SA 4.0
2024-02-05T20:36:58.200Z
2024-02-05T20:36:58.200Z
S. M.
<p>I have been studying the Exponential-Time Hypothesis, ETH, from this <a href="https://drive.google.com/file/d/1Yr5VuySJw79DVOnbBY0AQ6IjVJQzvTyo/view?usp=drivesdk" rel="nofollow noreferrer">paper</a>, there defined <span class="math-container">$s_k = \inf\{\delta \geq 0 | k\text{-}SAT \in RTIME[2^{\delta n}]\}$</span>.</p>
<p>But in that paper's page number 10, I see this theorem, <span class="math-container">$s_k \leq (1 − \Omega(k^{−1}))s_{\infty}.$</span></p>
<p>My question is how to prove this theorem, is there any sources are available?</p>
<p>And is it also possible to prove
<span class="math-container">$s_k$</span> strictly increases <span class="math-container">$(s_{k+1} &gt; s_k)$</span> for an infinite number of the values of <span class="math-container">$k?$</span> What hypothesis do we need for this? And Why?</p>
<p>Any help or hints are most welcomed.</p>
<p>Helpful reference maybe this <a href="https://drive.google.com/file/d/1iI6byUc6azTMOgRiCXIoE5sAK4J_rRop/view?usp=drivesdk" rel="nofollow noreferrer">paper</a>.</p>

CC BY-SA 4.0
2024-02-01T10:19:21.780Z
Can you email the author to ask?
Simd
CC BY-SA 4.0
2024-02-01T10:27:21.877Z
If there is no one in your department who can help, you will have to email one of those authors politely and ask.
Simd
<cc.complexity-theory><reference-request><lo.logic><sat><exp-time-algorithms>
Sparsification and critical clauses in SAT
S. M.
# Sparsification and critical clauses in SAT

(Asked by: username_0 on 2024-01-26)

I have been studying the Exponential-Time Hypothesis, ETH, from this [paper](https://drive.google.com/file/d/1Yr5VuySJw79DVOnbBY0AQ6IjVJQzvTyo/view?usp=drivesdk), there defined $s\_k = \inf\{\delta \geq 0 | k\text{-}SAT \in RTIME[2^{\delta n}]\}$.

But in that paper's page number 10, I see this theorem, $s\_k \leq (1 − \Omega(k^{−1}))s\_{\infty}.$

My question is how to prove this theorem, is there any sources are available?

And is it also possible to prove
$s\_k$ strictly increases $(s\_{k+1} > s\_k)$ for an infinite number of the values of $k?$ What hypothesis do we need for this? And Why?

Any help or hints are most welcomed.

Helpful reference maybe this [paper](https://drive.google.com/file/d/1iI6byUc6azTMOgRiCXIoE5sAK4J_rRop/view?usp=drivesdk).

**Tags:** cc.complexity-theory, reference-request, lo.logic, sat, exp-time-algorithms

> **Comments:**
> **username_1**: Can you email the author to ask?  
> **username_1**: If there is no one in your department who can help, you will have to email one of those authors politely and ask.  

---

## 1 answers

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

The partial answer 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.


---

