The existence and density of generalized complexity cores

Reviewer: Daniel M. Leivant

This paper studies a notion of proper hard core (phc), generalizing Lynch's notion of “complexity core.” For a set A and a collection C , an infinite H ? 9T A is a phc of A with respect to C if H :3Wd9T C is finite for all C ? C :3Wd9T P ( A) (where P is the power set operator). The paper's main result is that if C is countable and closed under finite variation and finite union, then every infinite A ? :.KC / C has a phc with respect to C . This is proven as follows: Say C A = Df C :3Wd9T P ( A) = { C i}- i. Set h k = min( C k ? C < k), where C < k = Df :3WD0I i< kC i and min(:3WC = Df 0. Let H = { h k} k. If H is infinite, then it is a phc, since H :3Wd9T C k ? 9T{ h i} i< k for all k. If H is finite, then :3WD9WC A = C < n for some n. A is then the union of n of the C i's and of the set H? = Df A ? :3WDQ C A. H? cannot be finite, for then A ? C by the closure conditions on C . Also, H? :3Wd9T C k = :3WCis finite for all k. So H ? is a phc. Each condition on C is shown to be necessary. Adding the requirement h k + 1 > h k in the proof yields a phc that is recursive in A if C A is an r.e. sequence of recursive sets. Special cases of the main result, for various complexity classes C , are shown to imply theorems on complexity cores by Even, Scho¨ning, Balca´zar, and others. The notion of phc is then related to sparseness, and results of Orponen and Scho¨ning are generalized, relating sparse complexity cores to Meyer-Paterson's notions of approximate polynomial time. Let C and A ? :.KC# / C be as above, with C A :3WC Let B ? 9T A. If every H ? 9T B which is a phc of A is sparse, then B ? 9T C :3WD9T D for some C ? C and sparse D. (This holds for an abstract notion of sparseness.) The work is significant in delineating general concepts and elementary constructions that underlie much of the previous literature on complexity cores.