The density and complexity of polynomial cores for intractable sets
- 31 July 1986
- journal article
- Published by Elsevier in Information and Control
- Vol. 70 (1) , 54-68
- https://doi.org/10.1016/s0019-9958(86)80024-9
Abstract
No abstract availableKeywords
This publication has 13 references indexed in Scilit:
- Bi-immune sets for complexity classesTheory of Computing Systems, 1985
- Hard-core theorems for complexity classesJournal of the ACM, 1985
- On the structure of sets in NP and other complexity classesTheoretical Computer Science, 1981
- Completeness, Approximation and DensitySIAM Journal on Computing, 1981
- A Note on Sparse Complete SetsSIAM Journal on Computing, 1979
- A linear-time algorithm for testing the truth of certain quantified boolean formulasInformation Processing Letters, 1979
- 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
- On the Structure of Polynomial Time ReducibilityJournal of the ACM, 1975
- Unit Refutations and Horn SetsJournal of the ACM, 1974