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 Answer 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$.

  • $\begingroup$ 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$? $\endgroup$
    – Soha
    Commented Jan 25, 2023 at 2:50
  • 1
    $\begingroup$ @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. $\endgroup$
    – D.W.
    Commented Jan 25, 2023 at 7:00
  • 2
    $\begingroup$ 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. $\endgroup$
    – Soha
    Commented Jan 31, 2023 at 11:54

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.