All Superlinear Inverse Schemes are coNP-Hard

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.
Conf. version was in MFCS 2004

Keywords

Computational Complexity, Cryptography and Security, F.1.3

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/32366

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0410023
 http://arxiv.org/abs/cs/0410023

Collections

arXiv