All superlinear inverse schemes are coNP-hard

DOI10.1016/J.TCS.2005.07.015MaRDI QIDQ2575753zbMATH OpenOpenAlexFDO

Authors Edith Hemaspaandra, Harald Hempel, Lane A. Hemaspaandra

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

Complexity theoryInverse problemsNPcoNP-hardnessCertificatesP-producible sets

Mathematics Subject Classification ID

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

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.

Recommendations

• Mathematical Foundations of Computer Science 2004
• Mathematical Foundations of Computer Science 2003
• Inverse NP problems
• \textsc{Inverse Hamiltonian cycle} and inverse \textsc{3Dimensional matching} are coNP-complete
• If P \(\neq\) NP then some strongly noninvertible functions are invertible

Cites work

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

Cited in

(4)

• Mathematical Foundations of Computer Science 2004
• \textsc{Inverse Hamiltonian cycle} and inverse \textsc{3Dimensional matching} are coNP-complete
• Inverse HAMILTONIAN CYCLE and Inverse 3-D MATCHING Are coNP-Complete
• Inverse NP problems

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)