All superlinear inverse schemes are coNP-hard

DOI10.1016/j.tcs.2005.07.015zbMath1079.68041arXivcs/0410023OpenAlexW2005128655MaRDI QIDQ2575753

Harald Hempel, Edith Hemaspaandra, Hemaspaandra, Lane A.

Publication date: 6 December 2005

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

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

zbMATH Keywords

Inverse problemsNPComplexity theorycoNP-hardnessCertificatesP-producible sets

Mathematics Subject Classification ID

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

Related Items (1)

\textsc{Inverse Hamiltonian cycle} and inverse \textsc{3Dimensional matching} are coNP-complete

Cites Work

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

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