<p>I think your confusion might come from misquoting the statement of ETH.</p>

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

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

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

<p>Now we can actually use the Sparsification Lemma to prove the following:</p>

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

<p>Assume that there is an algorithm $A$ which solves $3$-SAT in time $poly(m)\cdot  2^{o(n+m)}$. For any $\delta&gt;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.) </p>

<p>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)}\; .$$</p>

CC BY-SA 4.0
2018-06-23T01:57:09.433Z
2018-06-23T01:57:09.433Z
Alex Golovnev
<p>According to <a href="https://ac.els-cdn.com/S002200000191774X/1-s2.0-S002200000191774X-main.pdf?_tid=d04f312d-6a87-4b3b-93e2-e5acfad32803&amp;acdnat=1521302158_f1aa0b4e11c1eea38ef9d2dd5ad2aede" rel="noreferrer">R. Impagliazzo, R. Paturi and F. Zane, 2001</a> an instance of $k$-SAT is called <em>sparse</em> if $m = O(n)$ where $m$ denotes the number of clauses and $n$ the number of variables. The <em>Sparsifiction Lemma</em>, as mentioned in <a href="https://www.sciencedirect.com/science/article/pii/S0022000000917276" rel="noreferrer">R. Impagliazzo, R. Paturi, 2001</a> says:</p>

<blockquote>
  <p>[...] 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 [...]</p>
  
  <p>For all $\varepsilon &gt; 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.</p>
</blockquote>

<p>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 <a href="https://simons.berkeley.edu/sites/default/files/docs/4009/fernau-krebs-slides.pdf" rel="noreferrer">this talk</a>, the Exponential Time Hypothesis (ETH) says:</p>

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

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

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

<p>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?</p>

CC BY-SA 3.0
2018-03-17T23:44:58.747Z
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.
tranisstor
<cc.complexity-theory><np-hardness><lo.logic><sat>
Sparsification Lemma for k-SAT and Exponential Time Hypothesis
StefanH
# Sparsification Lemma for k-SAT and Exponential Time Hypothesis

(Asked by: username_0 on 2018-03-17)

According to [R. Impagliazzo, R. Paturi and F. Zane, 2001](https://ac.els-cdn.com/S002200000191774X/1-s2.0-S002200000191774X-main.pdf?_tid=d04f312d-6a87-4b3b-93e2-e5acfad32803&acdnat=1521302158_f1aa0b4e11c1eea38ef9d2dd5ad2aede) 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](https://www.sciencedirect.com/science/article/pii/S0022000000917276) 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](https://simons.berkeley.edu/sites/default/files/docs/4009/fernau-krebs-slides.pdf), 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?

**Tags:** cc.complexity-theory, np-hardness, lo.logic, sat

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2018-06-23. Score: 10 | Accepted answer

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)}\; .$$


---

