All superlinear inverse schemes are coNP-hard
From MaRDI portal
Publication:2575753
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
Related Items (1)
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