On inefficient special cases of NP-complete problems
- 31 March 1989
- journal article
- Published by Elsevier in Theoretical Computer Science
- Vol. 63 (3) , 239-252
- https://doi.org/10.1016/0304-3975(89)90015-7
Abstract
No abstract availableKeywords
This publication has 14 references indexed in Scilit:
- OnP-subset structuresTheory of Computing Systems, 1987
- The existence and density of generalized complexity coresJournal of the ACM, 1987
- A classification of complexity core latticesTheoretical Computer Science, 1986
- The density and complexity of polynomial cores for intractable setsInformation and Control, 1986
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NPTheoretical Computer Science, 1985
- Nonlevelable sets and immune sets in the accepting density hierarchy inNPTheory of Computing Systems, 1985
- Bi-immune sets for complexity classesTheory of Computing Systems, 1985
- Sparse complete sets for NP: Solution of a conjecture of Berman and HartmanisJournal of Computer and System Sciences, 1982
- On Isomorphisms and Density of $NP$ and Other Complete SetsSIAM Journal on Computing, 1977
- On Reducibility to Complex or Sparse SetsJournal of the ACM, 1975