On inefficient special cases of NP-complete problems
From MaRDI portal
Publication:1823688
DOI10.1016/0304-3975(89)90015-7zbMath0681.68063MaRDI QIDQ1823688
Publication date: 1989
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(89)90015-7
68Q25: Analysis of algorithms and problem complexity
Cites Work
- Unnamed Item
- Unnamed Item
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
- A classification of complexity core lattices
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- A Note on Sparse Complete Sets
- Bi-immune sets for complexity classes
- Nonlevelable sets and immune sets in the accepting density hierarchy inNP
- The density and complexity of polynomial cores for intractable sets
- Optimal Approximations and Polynomially Levelable Sets
- OnP-subset structures
- On Reducibility to Complex or Sparse Sets
- On Isomorphisms and Density of $NP$ and Other Complete Sets