The existence and density of generalized complexity cores
- 1 July 1987
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 34 (3) , 718-730
- https://doi.org/10.1145/28869.28880
Abstract
If C is a class of sets and A is not in C , then an infinite set H is a proper hard core for A with respect to C , if H ⊆ A and for every C ε C such that C ⊆ A , C ⋒ H is finite. It is shown that if C is a countable class of sets of strings that is closed under finite union and finite variation, then every infinite set not in C has a proper hard core with respect to C . In addition, the density of such generalized complexity cores is studied.Keywords
This publication has 12 references indexed in Scilit:
- A classification of complexity core latticesTheoretical Computer Science, 1986
- Sparse Sets, Lowness and HighnessSIAM Journal on Computing, 1986
- The density and complexity of polynomial cores for intractable setsInformation and Control, 1986
- Optimal Approximations and Polynomially Levelable SetsSIAM Journal on Computing, 1986
- Bi-immune sets for complexity classesTheory of Computing Systems, 1985
- Hard-core theorems for complexity classesJournal of the ACM, 1985
- On small generatorsTheoretical Computer Science, 1984
- A low and a high hierarchy within NPJournal of Computer and System Sciences, 1983
- Oracle-dependent properties of the lattice of NP setsTheoretical Computer Science, 1983
- On Reducibility to Complex or Sparse SetsJournal of the ACM, 1975