2026-07-072026-07-07http://salesiana.dossiersoluciones.com/handle/123456789/32366How 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 2004Computational ComplexityCryptography and SecurityF.1.3text