Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Witness length:
TR06-022 | 17th February 2006
Danny Harnik, Moni Naor

On the Compressibility of NP Instances and Cryptographic Applications

Revisions: 1

We initiate the study of the compressibility of NP 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
more >>>

ISSN 1433-8092 | Imprint