Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses
Dieter van Melkebeek
Wednesday, September 30, 2009
4:00 PM, 3310 CS
Consider the following two-player 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>=3 and positive real epsilon we show that if
satisfiability for n-variable d-CNF formulas has a protocol of
cost O(n^{d-\epsilon}) then coNP is in NP/poly, which implies that the
polynomial-time hierarchy collapses to the third level. The result
even holds for conondeterministic protocols, and is tight
as there exists a trivial deterministic 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, including
sparsification, probabilistically checkable proofs, instance
compression, and kernelization in parameterized complexity.
Joint work with H. Dell.
Additional CS events.
|
