1
$\begingroup$

I have been studying the Exponential-Time Hypothesis, ETH, from this paper, 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.

Improve this question
$\endgroup$
2
  • $\begingroup$ Can you email the author to ask? $\endgroup$
    – Simd
    Commented Feb 1 at 10:19
  • $\begingroup$ If there is no one in your department who can help, you will have to email one of those authors politely and ask. $\endgroup$
    – Simd
    Commented Feb 1 at 10:27

1 Answer 1

Reset to default
1
$\begingroup$

The partial answer existed in the paper, On the Complexity of k-SAT by Russell Impagliazzo and Ramamohan Paturi, 374 page, Theorem 3.

Improve this answer
$\endgroup$

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.