NewEvery arXiv paper, its researchers & institutions — mapped.
paper

All Superlinear Inverse Schemes are coNP-Hard

arXiv:cs/0410023

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.

Conf. version was in MFCS 2004