Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR07-096 | 8th October 2007 00:00

Infeasibility of Instance Compression and Succinct PCPs for NP



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.

ISSN 1433-8092 | Imprint