The existence and density of generalized complexity cores
Ronald V. Book, Ding‐Zhu Du · Journal of the ACM · 1987
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.