1
$\begingroup$

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$?
Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\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
    Jan 25 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. ♦
    Jan 25 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
    Jan 31 at 11:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.