Structural properties of complexity classes (immunity, core)
David A. Russo · 1985
Structural properties of complexity classes are investigated via the concept of immunity, and more generally that of a complexity core. New relativizations of many common complexity classes (e.g., P, NP (INTERSECT) co-NP, and the probabilistic complexity classes) are provided which pairwise separate these classes in such a way that there is an infinite set in one class that is immune to the other. For example, we show that there exists a recursive oracle A such that ZPP(A) contains an infinite P(A)-immune set. For any recursive set A that is not in P and not P-immune, the lattice of all proper recursive complexity cores (modulo the finite sets) for A is isomorphic to the lattice of P-subsets (modulo the finite sets) of A. Moreover, for any recursive set there are exactly three different possible recursive proper complexity core lattices. Thus, we have a classification for all recursive sets A of the lattice of recursive complexity cores (modulo the finite sets) of A. In particular, all P-levelable sets have isomorphic proper complexity core lattices (modulo the finite sets); and so, by the first results, they have isomorphic P-subset lattices (modulo the finite sets). The property of P-levelability has an interesting connection with the Meyer and Paterson notion of approximation; if a recursive set A is P-levelable and then given any approximation of A there is another approximation of A which improves the first on an infinite set. All (LESSTHEQ)(,m)('P)-complete(' )sets for EXPTIME are P-levelable. If P (NOT=) PSPACE then all (LESSTHEQ)('log)-complete(' )sets for PSPACE are P-levelable. If P (NOT=) NP any (LESSTHEQ)(,m)('P)-complete(' )set for NP that is either paddable or k-creative is P-levelable. Thus, all known(' )(LESSTHEQ)(,m)('P)-complete sets for NP are P-levelable.