Article ID Journal Published Year Pages File Type
9657751 Theoretical Computer Science 2005 14 Pages PDF
Abstract
How hard is it to invert NP-problems? We show that all superlinearly certified inverses of NP problems are coNP-hard. To do so, we develop a novel proof technique that builds diagonalizations against certificates directly into a circuit.
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
All superlinear inverse schemes are coNP-hard
Authors
, , ,