## Abstract

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.

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.

Original language | English |
---|---|

Number of pages | 24 |

Journal | Electronic Colloquium on Computational Complexity (ECCC) |

Volume | 14 |

Issue number | 096 |

Publication status | Published - 8 Oct 2007 |