Infeasibility of instance compression and succinct PCPs for NP

The OR-SAT problem asks, given Boolean formulae ${?}_1,\dots ,{?}_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 $\mathsf{NP}?\mathsf{coNP}/\mathrm{poly}$, and the Polynomial-Time Hierarchy collapses. This result settles an open problem proposed by Bodlaender et al. (2008) [6] and Harnik and Naor (2006) [20] and has a number of implications. (i) A number of parametric $\mathsf{NP}$ problems, including Satisfiability, Clique, Dominating Set and Integer Programming, are not instance compressible or polynomially kernelizable unless $\mathsf{NP}?\mathsf{coNP}/\mathrm{poly}$. (ii) Satisfiability does not have PCPs of size polynomial in the number of variables unless $\mathsf{NP}?\mathsf{coNP}/\mathrm{poly}$. (iii) 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. (iv) (Buhrman–Hitchcock) There are no subexponential-size 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.