Infeasibility of instance compression and succinct PCPs for NP

By Lance Fortnow, R. Santhanam. Journal of computer and system sciences (Print), 2007

342 citations recorded by the source corpus.

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 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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/a1fb24027cf0bac87da65c3b8d4716fba6dbe491

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

On problems without polynomial kernels (2009, methodology): “We ﬁrst introduce this notion, and then use an argument of Fortnow and Santhanam [27] to show that a distillation algorithm for any NP-complete problem implies the collapse of the polynomial hierarchy to at least three levels.”
Zero-Knowledge Proofs on Secret-Shared Data via Fully Linear PCPs (2019, background): “Standard PCPs with succinctness properties cannot exist unless the polynomial hierarchy collapses [49].”