TR07-096 Authors: Lance Fortnow, Rahul Santhanam

Publication: 8th October 2007 08:13

Downloads: 2107

Keywords:

We study the notion of "instance compressibility" of NP problems [Harnik-Naor06], closely related to the notion of kernelization in parameterized complexity theory [Downey-Fellows99, Flum-Grohe06, Niedermeier06]. A language $L$ in NP is instance compressible if there

is a polynomial-time computable function $f$ and a set $A$ such that

for each instance $x$ of $L$, $f(x)$ is of size polynomial in the {\it witness size} of $x$, and $f$ reduces $L$ to $A$.

We prove that SAT is not instance compressible unless NP is contained in

coNP/poly, and the Polynomial Hierarchy collapses. This result settles an open problem posed by [Harnik-Naor06] and [Downey07], and has a number of implications:

1. A number of parametric NP problems, including SAT, Clique, DominatingSet and IntegerProgramming, are not polynomially kernelizable unless NP is contained in coNP/poly.

2. SAT does not have "succinct PCPs", i.e., PCPs of size polynomial in the number of variables, unless NP is contained in coNP/poly.

3. An approach of Harnik and Naor to constructing collision-resistant hash functions from one-way functions is inviable in its present form.

4. (Burhman) There are no sub-exponential size complete sets for NP or coNP unless NP is contained in coNP/poly.