## Abstract

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 2n−n CNFs each having a linear number of clauses for any 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 nk which cannot be written as a sub-exponential size disjunction of CNFs of size nk. 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)=(nlog(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 2n−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(2n) for some fixed 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(+o(1))n).

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)=(nlog(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 2n−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(2n) for some fixed 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(+o(1))n).

Original language | English |
---|---|

Pages (from-to) | 131-143 |

Number of pages | 12 |

Journal | Electronic Colloquium on Computational Complexity (ECCC) |

Volume | 18 |

Publication status | Published - 29 Nov 2011 |