ECCC-Report TR07-096https://eccc.weizmann.ac.il/report/2007/096Comments and Revisions published for TR07-096en-usMon, 08 Oct 2007 08:13:28 +0200
Paper TR07-096
| Infeasibility of Instance Compression and Succinct PCPs for NP |
Lance Fortnow,
Rahul Santhanam
https://eccc.weizmann.ac.il/report/2007/096We 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.
Mon, 08 Oct 2007 08:13:28 +0200https://eccc.weizmann.ac.il/report/2007/096