All Superlinear Inverse Schemes are coNP-Hard
<|reference_start|>All Superlinear Inverse Schemes are coNP-Hard: 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.<|reference_end|>
@article{hemaspaandra2004all,
    title={All Superlinear Inverse Schemes are coNP-Hard},
    author={Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel},
    journal={arXiv preprint arXiv:cs/0410023},
    year={2004},
    number={URCS-TR-2004-841},
    archivePrefix={arXiv},
    eprint={cs/0410023},
    primaryClass={cs.CC cs.CR}
}