Infeasibility of instance compression and succinct PCPs for NP

Lance Fortnow, Rahul Santhanam

Research output: Chapter in Book/Report/Conference proceedingConference contribution


The OR-SAT problem asks, given Boolean formulae φ1, . . . , φm each of size at most n, whether at least one of the φi’s is satisfiable.

We show that there is no reduction from OR-SAT to any set A where the length of the output is bounded by a polynomial in n, unless NP ⊆ coNP/poly, and the Polynomial-Time Hierarchy collapses. This result settles an open problem proposed by Bodlaender et. al. [4] and Harnik and Naor [15] and has a number of implications.

• A number of parametric NP problems, including Satisfiability, Clique, Dominating Set and Integer Programming, are not instance compressible or polynomially kernelizable unless NP ⊆ coNP/poly.

• Satisfiability does not have PCPs of size polynomial in the number of variables unless NP ⊆ coNP/poly.

• An approach of Harnik and Naor to constructing collision-resistant hash functions from one-way functions is unlikely to be viable in its present form.

• (Buhrman-Hitchcock) There are no subexponentialsize hard sets for NP unless NP is in co-NP/poly.

We also study probabilistic variants of compression, and show various results about and connections between these variants. To this end, we introduce a new strong derandomization hypothesis, the Oracle Derandomization Hypothesis,
and discuss how it relates to traditional derandomization assumptions.

Original languageEnglish
Title of host publicationProceedings of the 40th annual ACM Symposium on Theory of Computing
Place of PublicationNew York, NY, USA
Number of pages10
ISBN (Print)978-1-60558-047-0
Publication statusPublished - 2008

Publication series

NameSTOC '08


  • cryptography
  • instance compression
  • parameterized complexity
  • polynomial hierarchy
  • succinct PCPs


Dive into the research topics of 'Infeasibility of instance compression and succinct PCPs for NP'. Together they form a unique fingerprint.

Cite this