Infeasibility of Instance Compression and Succinct PCPs for NP

Lance Fortnow, Rahul Santhanam

Research output: Contribution to journalArticlepeer-review

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.
Original languageEnglish
Number of pages24
JournalElectronic Colloquium on Computational Complexity (ECCC)
Volume14
Issue number096
Publication statusPublished - 8 Oct 2007

Fingerprint Dive into the research topics of 'Infeasibility of Instance Compression and Succinct PCPs for NP'. Together they form a unique fingerprint.

Cite this