-1
$\begingroup$

I followed from this question.

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

$\endgroup$
4
  • 1
    $\begingroup$ Simultaneously cross-posted at mathoverflow.net/questions/463578/… . You were told many times before this is against the site rules. $\endgroup$ Feb 6 at 10:08
  • $\begingroup$ @EmilJeřábek deleted in mathoverflow. $\endgroup$
    – S. M.
    Feb 6 at 10:25
  • 1
    $\begingroup$ @EmilJeřábek please check my first part answer correct or not. If not please suggest me how to approach. And also please give me some suggestions for second part also. $\endgroup$
    – S. M.
    Feb 9 at 22:35
  • $\begingroup$ 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 math.stackexchange.com or cs.stackexchange.com . $\endgroup$ Feb 10 at 8:57

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 10 at 9:01

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.