All superlinear inverse schemes are coNP-hard

DOI10.1016/J.TCS.2005.07.015zbMATH Open1079.68041arXivcs/0410023OpenAlexW2005128655MaRDI QIDQ2575753FDOQ2575753

Harald Hempel, Edith Hemaspaandra, Lane A. Hemaspaandra

Publication date: 6 December 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/cs/0410023

zbMATH Keywords

Complexity theoryInverse problemsNPcoNP-hardnessCertificatesP-producible sets

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The polynomial-time hierarchy
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• The complexity of facets (and some facets of complexity)
• The Boolean Hierarchy I: Structural Properties
• The Boolean Hierarchy II: Applications
• Complete sets and the polynomial-time hierarchy
• Mathematical Foundations of Computer Science 2003
• The complexity theory companion
• Sets with small generalized Kolmogorov complexity
• Continuous optimization problems and a polynomial hierarchy of real functions
• On the complexity of ranking
• On the Computational Complexity of Small Descriptions
• Mathematical Foundations of Computer Science 2004

Cited In (2)

• Mathematical Foundations of Computer Science 2004
• \textsc{Inverse Hamiltonian cycle} and inverse \textsc{3Dimensional matching} are coNP-complete

This page was built for publication: All superlinear inverse schemes are coNP-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2575753)