Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > QUANTUM COMPRESSION:
Reports tagged with Quantum compression:
TR12-112 | 7th September 2012
Andrew Drucker

#### New Limits to Classical and Quantum Instance Compression

Revisions: 3

Given an instance of a hard decision problem, a limited goal is to $compress$ that instance into a smaller, equivalent instance of a second problem. As one example, consider the problem where, given Boolean formulas $\psi^1, \ldots, \psi^t$, we must determine if at least one $\psi^j$ is satisfiable. An \$OR-compression ... more >>>

ISSN 1433-8092 | Imprint