TR11-131 Authors: Rahul Santhanam, Srikanth Srinivasan

Publication: 29th September 2011 15:38

Downloads: 3929

Keywords:

Impagliazzo, Paturi and Zane (JCSS 2001) proved a sparsification lemma for $k$-CNFs:

every k-CNF is a sub-exponential size disjunction of $k$-CNFs with a linear

number of clauses. This lemma has subsequently played a key role in the study

of the exact complexity of the satisfiability problem. A natural question is

whether an analogous structural result holds for CNFs or even for broader

non-uniform classes such as constant-depth circuits or Boolean formulae.

We prove a very strong negative result in this connection: For every superlinear

function $f(n)$, there are CNFs of size $f(n)$ which cannot be written as

a disjunction of $2^{n- \varepsilon n}$ CNFs each having a linear number of

clauses for any $\varepsilon > 0$. We also give a hierarchy of such non-sparsifiable CNFs: For every

$k$, there is a $k'$ for which there are CNFs of size $n^{k'}$ which cannot

be written as a sub-exponential size disjunction of CNFs of size $n^{k}$.

Furthermore, our lower bounds hold not just against CNFs but against an {\it arbitrary}

family of functions as long as the cardinality of the family is appropriately

bounded.

As by-products of our result, we make progress both on questions about

circuit lower bounds for depth-3 circuits and satisfiability algorithms for

constant-depth circuits. Improving on a result of Impagliazzo, Paturi and

Zane, for any $f(n) = \omega(n \log(n))$, we define a pseudo-random function generator with seed length $f(n)$

such that with high probability, a function in the output of this generator

does not have depth-3 circuits of size $2^{n-o(n)}$ with bounded bottom fan-in.

We show that if we could decrease the seed length of our generator below

$n$, we would get an explicit function which does not have linear-size

logarithmic-depth series-parallel circuits, solving a long-standing open question.

Motivated by the question of whether CNFs sparsify into bounded-depth circuits,

we show a {\it simplification} result for bounded-depth circuits: any bounded-depth circuit of linear size can be written as a sub-exponential size disjunction of linear-size

constant-width CNFs. As a corollary, we show that if there is an algorithm for

CNF satisfiability which runs in time $O(2^{\alpha n})$ for some fixed

$\alpha < 1$ on CNFs of linear size, then there is an algorithm for

satisfiability of linear-size constant-depth circuits which runs in time

$O(2^{(\alpha + o(1))n})$.