## Abstract

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 language | English |
---|---|

Title of host publication | Proceedings of the 40th annual ACM Symposium on Theory of Computing |

Place of Publication | New York, NY, USA |

Publisher | ACM |

Pages | 133-142 |

Number of pages | 10 |

ISBN (Print) | 978-1-60558-047-0 |

DOIs | |

Publication status | Published - 2008 |

### Publication series

Name | STOC '08 |
---|---|

Publisher | ACM |

## Keywords

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