On the Limits of Sparsification ⋆
Rahul Santhanam, Srikanth Srinivasan · 2013
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 2 n−ε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 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 arbitrary family