# Understanding the Strong Exponential Time Hypothesis

Let $$n$$ be the number of variables in the input formula and $$m$$ the number of clauses. Define $$s_k = \inf\{\delta : k\text{-SAT can be solved in } 2^{\delta n} \text{ time}\}$$. The strong exponential time hypothesis says that $$\lim \limits_{k \to \infty} s_k=1$$. I have two questions here:

1. What if the input size is very large, say, $$m=\Theta(3^n)$$? Simply reading the input formula needs $$\omega(2^n)$$ time. In this case, $$\lim \limits_{k \to \infty} s_k$$ would be larger than $$1$$.
2. A paper in SAT Conference 2021 says, "The strong exponential time hypothesis conjectures that the SAT problem cannot be solved in time $$O^*(c^n)$$ for some constant $$c<2$$." I haven't found the equivalent statement in Impagliazzo and Paturi's original paper. Why is this statement equivalent to $$\lim \limits_{k \to \infty} s_k = 1$$?

1. That can't happen. The maximum number of distinct possible clauses is $$(2n)^k = O(n^k)$$, which is polynomial in $$n$$ (since here $$k$$ is fixed).

2. Here I imagine that there notation $$O^*(c^n)$$ probably refers to something like $$O((nL)^{O(1)} c^n)$$. If you could solve SAT in $$O(1.5^n)$$ time, then you could solve $$k$$-SAT in $$O(1.5^n)$$ time for all $$k$$, thus $$s_k \le \log_2 1.5 < 1$$ for all $$k$$, we cannot have $$s_k \to 1$$.

• Thanks a lot. Let $A$ denote the statement that $s_k \to 1$, and $B$ denote the equivalent statement. However, your answer to question 2 only shows that $\neg B \implies \neg A$. Could you please explain why $\neg A \implies \neg B$, i.e., if $\lim \limits_{k\to\infty} s_k < 1$, we can solve SAT in $O^*(c^n)$ time where $c<2$?
– Soha
Jan 25 at 2:50
• @Soha, My answer proves that $s_k \to 1$ implies SAT can't be solved in $O^*(c^n)$ for $c<2$ (by showing that if SAT can be solved in $O^*(c^n)$ for $c<2$, then $s_k \not\to 1$, the contrapositive). I don't know whether it is possible to prove the other direction.
– D.W.
Jan 25 at 7:00
• I think the following may be a correct way to prove the other direction. For an SAT instance, each clause may contain no more than $n$ literals, which means it cannot be harder than an $n$-SAT instance. So if $s_k \to s_{\infty} \ne 1$, we would be able to solve the instance with an $n$-SAT solver in $O^*(2^{s_{\infty}n})$ time.
– Soha
Jan 31 at 11:54