All Superlinear Inverse Schemes are coNP-Hard
Hemaspaandra, Edith · Hemaspaandra, Lane A. · Hempel, Harald
Original · EN
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.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.