Dense and non-dense families of complexity classes

Let Φ be any abstract measure of computational complexity, and let L denote the specific measure of memory resource (tape) on one tape Turing machines. Denote by Rt () Φ the class of all total functions whose Φ-complexity is bounded by the function t () almost everywhere. Call such classes Φ-complexity classes. We are interested in relationships among these classes, under proper set inclusion (⊂). In other words, we are interested in the partially ordered structure ≪ ΣΦ, ⊆ ≫ where ΣΦ = Rt () Φ|t () is recursive is called the family of Φ-complexity classes. Of special interest is the subfamily ΩΦ = RΦi () Φ | Φi () is total, called the family of exact Φ-complexity classes. We show that ΣL and ΩL are dense under ⊂ for sufficiently large bounds t (), but ΩL is not dense in ΣL. We also construct measures Φ for which ΣΦ and ΩΦ are non-dense, for which ΣΦ is dense but ΩΦ is not, for which ΩΦ is dense but ΣΦ is not and for which ΩΦ is dense in ΣΦ. Thus density is not a measure invariant property of ΣΦ or ΩΦ. These are the first examples of important structural properties of these families which are not measure invariant.