All Superlinear Inverse Schemes are coNP-Hard

Simple item page
dc.creatorHemaspaandra, Edith
dc.creatorHemaspaandra, Lane A.
dc.creatorHempel, Harald
dc.date2004-10-12
dc.date.accessioned2026-07-07T03:21:51Z
dc.date.available2026-07-07T03:21:51Z
dc.descriptionHow 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.
dc.descriptionConf. version was in MFCS 2004
dc.identifierhttps://arxiv.org/abs/cs/0410023
dc.identifierhttp://arxiv.org/abs/cs/0410023
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/32366
dc.subjectComputational Complexity
dc.subjectCryptography and Security
dc.subjectF.1.3
dc.titleAll Superlinear Inverse Schemes are coNP-Hard
dc.typetext

Files

Collections

arXiv