A simple proof that AND-compression of NP-complete problems is hard
Holger Dell · arXiv (Cornell University) · 2014
Drucker [1] proved the following result: Unless the unlikely complexity-theoretic collapse coNP ⊆ NP/poly occurs, there is no AND-compression for SAT. The result has implications for the compressibility and kernelizability of a whole range of NP-complete parameterized problems. We present a simple proof of this result. An AND-compression is a deterministic polynomial-time algorithm that maps a set of SAT-instances x1,..., xt to a single SAT-instance y of size poly(maxi |xi|) such that y is satisfiable if and only if all xi are satisfiable. The “AND ” in the name stems from the fact that the predicate “y is satisfiable ” can be written as the AND of all predicates “xi is satisfiable”. Drucker’s result complements the result by Bodlaender et al. [2] and Fortnow and Santhanam [3], who proved the analogous statement for OR-compressions, and Drucker’s proof not only subsumes that result but also extends it to randomized compression algorithms that are allowed to have a certain probability of failure. The overall structure of our proof is similar to the arguments of Ko [4] for P-selective sets, which use the fact that tournaments have dominating sets of logarith-mic size. We generalize this fact to hypergraph tournaments. For the information-theoretic part of the proof, we consider a natural generalization of the average noise sensitivity of a Boolean function, which is bounded for compressive maps. We prove this with mechanical calculations that involve the Kullback–Leibler divergence. 1