- Authors: H. Dell and D. van Melkebeek.
- Reference:
*Journal of the ACM*, 61(4), Article 23, 27 pages, 2014. - Earlier version:
- H. Dell and D. van Melkebeek.
Satisfiability
Allows No Nontrivial Sparsification
Unless The Polynomial-Time Hierarchy Collapses.
In
*Proceedings of the 42nd ACM Symposium on Theory of Computing*, pages 251-260, 2010.

- H. Dell and D. van Melkebeek.
Satisfiability
Allows No Nontrivial Sparsification
Unless The Polynomial-Time Hierarchy Collapses.
In

For any integer *d* ≥ 3 and positive real ε we show that
if satisfiability for *n*-variable *d*-CNF formulas has a protocol
of cost O(*n*^{d-ε}) then coNP is in NP/poly,
which implies that
the polynomial-time hierarchy collapses to its third level. The result
even holds when the first player is conondeterministic, and is tight as there
exists a trivial deterministic protocol for ε = 0. Under the
hypothesis that coNP is not in NP/poly, our result implies tight lower
bounds for parameters of interest in several areas, namely
sparsification, kernelization in parameterized complexity, lossy
compression, and probabilistically checkable proofs.

By reduction, similar results hold for other NP-complete problems.
For the vertex cover problem on *n*-vertex *d*-uniform hypergraphs,
the above statement holds for any integer *d* ≥ 2. The case
*d*=2
implies that no NP-hard vertex deletion problem based on a graph
property that is inherited by subgraphs can have kernels consisting of
O(*k*^{2-ε}) edges unless coNP is in NP/poly,
where *k* denotes the size of the deletion set. Kernels consisting of
O(*k*^{2}) edges are
known for several problems in the class, including vertex cover,
feedback vertex set, and bounded-degree deletion.

dieter@cs.wisc.edu