5
$\begingroup$

According to R. Impagliazzo, R. Paturi and F. Zane, 2001 an instance of $k$-SAT is called sparse if $m = O(n)$ where $m$ denotes the number of clauses and $n$ the number of variables. The Sparsifiction Lemma, as mentioned in R. Impagliazzo, R. Paturi, 2001 says:

[...] that an arbitrary $k$-CNF can be expressed (in subexponential time) as the disjunction of a subexponential number of linear size $k$-CNFs. More precisely [...]

For all $\varepsilon > 0$, $k$-CNF $F$ can be written as the disjunction of at most $2^{\varepsilon n}$ $k$-CNF $F_i$ such that $F_i$ contains each variable in at most $c(k,\varepsilon)$ clauses for some function $c$. Moreover, this reduction takes at most $poly(n) 2^{\varepsilon n}$ time.

In the above reduction, each $k$-CNF $F_i$ has at most $c(k,\varepsilon)n$ many clauses, hence is sparse in the above sense. According to this talk, the Exponential Time Hypothesis (ETH) says:

$3$-SAT instances (with $n$ variables and $m$ clauses) cannot be solved in time $O(poly(n) 2^{o(n)})$.

(the $O^{\ast}$-star notation just suppresses polynomials). And it says that the Sparsification Lemma is equivalent to:

If ETH holds, then $3$-SAT instances cannot be solved in time $O(poly(n) 2^{o(n+m)})$.

I do not understand the second claim, so I am asking if anyone could please explain why this is a statement of the Sparsification Lemma, what has it to do with the Lemma as stated before?

$\endgroup$
  • 1
    $\begingroup$ The statement is a corollary from the sparsification lemma: We prove by contradiction. Suppose 3SAT can be solved in time $O^*(2^{o(n+m)})$ using a very fast algorithm. Consider a 3SAT instance with $m = \omega(n)$ clauses. Apply the sparsification lemma to obtain $2^{\varepsilon n}$ 3SAT instances of only $O(n)$ clauses. Now apply the very fast algorithm to each of these instances. This in total takes times $O^*(2^{\varepsilon n + o(n)}) = O^*(2^{\varepsilon n})$. Thus, we have found an algorithm which solves 3SAT in time $O(2^{\varepsilon n})$ for any $\varepsilon > 0$. This violates ETH. $\endgroup$ – tranisstor Mar 17 '18 at 23:44
8
$\begingroup$

I think your confusion might come from misquoting the statement of ETH.

$3$-SAT instances (with $n$ variables and $m$ clauses) cannot be solved in time $poly(n)\cdot 2^{o(n)}$.

This statement is not ETH, but rather its weak (but often very useful) corollary. The ETH claims the following:

There exists a $\delta>0$ such that no algorithm with running time $poly(m)\cdot 2^{\delta n}$ can solve $3$-SAT.

Now we can actually use the Sparsification Lemma to prove the following:

If ETH holds, then $3$-SAT instances cannot be solved in time $poly(m)\cdot 2^{o(n+m)}$.

Assume that there is an algorithm $A$ which solves $3$-SAT in time $poly(m)\cdot 2^{o(n+m)}$. For any $\delta>0$, we'll construct an algorithm $B_\delta$ which solves $3$-SAT in time $poly(m)\cdot 2^{\delta n+o(n)}$. (This contradicts ETH and finishes the proof.)

First, the algorithm $B_\delta$ takes an input formula $\phi$, applies the Sparsification Lemma with $\varepsilon=\delta$, and in time $poly(m)\cdot 2^{\delta n}$ produces $2^{\delta n}$ formulas $\phi_i$, such that $\phi$ is satisfiable if and only if $\exists i\colon \phi_i$ is satisfiable. Now the algorithm $B_\delta$ solves each of $\phi_i$ using the algorithm $A$. Note that by Sparsification Lemma the number of clauses in $\phi_i$ is $O(n)$, thus, each $\phi_i$ is solved by $A$ in time $2^{o(n)}$. Now the total running time of $B_\delta$ is $$poly(m)\cdot 2^{\delta n} + poly(m)\cdot 2^{\delta n}2^{o(n)}=poly(m)\cdot 2^{\delta n+o(n)}\; .$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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