What is a hard instance of a computational problem?
- 1 January 1986
- book chapter
- Published by Springer Nature
- p. 197-217
- https://doi.org/10.1007/3-540-16486-3_99
Abstract
No abstract availableKeywords
This publication has 11 references indexed in Scilit:
- The density and complexity of polynomial cores for intractable setsInformation and Control, 1986
- Optimal Approximations and Polynomially Levelable SetsSIAM Journal on Computing, 1986
- 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
- Hard-core theorems for complexity classesJournal of the ACM, 1985
- The structure of polynomial complexity coresPublished by Springer Nature ,1984
- Generalized Kolmogorov complexity and the structure of feasible computationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- On sparse sets in NP–PInformation Processing Letters, 1983
- Some connections between nonuniform and uniform complexity classesPublished by Association for Computing Machinery (ACM) ,1980
- On Reducibility to Complex or Sparse SetsJournal of the ACM, 1975