On the Compressibility of NP Instances and Cryptographic Applications

 Danny Harnik and Moni Naor

Abstract:

We study compression that preserves the solution to an instance of a problem rather than preserving the instance itself. Our focus is on the compressibility of NP decision problems. We consider NP problems that have long instances but relatively short witnesses. The question is, can one efficiently compress an instance and store a shorter representation that maintains the information of whether the original input is in the language or not. We want the length of the compressed instance to be polynomial in the length of the witness and polylog in the length of original input. We discuss the differences between this notion and similar notions from parameterized complexity. Such compression enables to succinctly store instances until a future setting will allow solving them, either via a technological or algorithmic breakthrough or simply until enough time has elapsed.

We investigate when such compression is possible and give a new classification of NP with respect to this compression; we call this the VC hierarchy. The hierarchy is based on a new type of reduction called W-reduction and there are compression-complete problems for each class.

Our motivation for studying this issue stems from the vast cryptographic implications we show for compressibility. For example, we say that SAT is compressible if given a formula consisting of m clauses on n variables it is possible to come up with an equivalent (w.r.t satisfiability) formula of size at most p(n, log m) for some polynomial p(,). If SAT is compressible, then:

Paper: Postscript , gzipped Postscript. PDF Slides: ppt


Related On-Line Papers:

Back to On-Line Publications

Back Home