Dell, Holger ;
van Melkebeek, Dieter
Satisfiability Allows No Nontrivial Sparsification Unless The PolynomialTime Hierarchy Collapses
Abstract
Consider the following twoplayer communication process to decide a
language $L$: The first player holds the entire input $x$ but is
polynomially bounded; the second player is computationally unbounded
but does not know any part of $x$; their goal is to cooperatively
decide whether $x$ belongs to $L$ at small cost, where the cost
measure is the number of bits of communication from the first player
to the second player.
For any integer $d geq 3$ and positive real $epsilon$ we show that
if satisfiability for $n$variable $d$CNF formulas has a protocol of
cost $O(n^{depsilon})$ then coNP is in NP/poly, which implies that
the polynomialtime hierarchy collapses to its third level. The result
even holds when the first player is conondeterministic, and is tight as
there exists a trivial protocol for $epsilon = 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 NPcomplete problems.
For the vertex cover problem on $n$vertex $d$uniform hypergraphs,
the above statement holds for any integer $d geq 2$. The case $d=2$
implies that no NPhard vertex deletion problem based on a graph
property that is inherited by subgraphs can have kernels consisting of
$O(k^{2epsilon})$ 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 boundeddegree deletion.
BibTeX  Entry
@InProceedings{dell_et_al:DSP:2010:2504,
author = {Holger Dell and Dieter van Melkebeek},
title = {Satisfiability Allows No Nontrivial Sparsification Unless The PolynomialTime Hierarchy Collapses},
booktitle = {Parameterized complexity and approximation algorithms},
year = {2010},
editor = {Erik D. Demaine and MohammadTaghi Hajiaghayi and D{\'a}niel Marx},
number = {09511},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Schloss Dagstuhl  LeibnizZentrum fuer Informatik, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2504},
annote = {Keywords: Sparsification, Kernelization, Parameterized Complexity, Probabilistically Checkable Proofs, Satisfiability, Vertex Cover}
}
Keywords: 

Sparsification, Kernelization, Parameterized Complexity, Probabilistically Checkable Proofs, Satisfiability, Vertex Cover 
Seminar: 

09511  Parameterized complexity and approximation algorithms

Issue date: 

2010 
Date of publication: 

11.03.2010 