Dense and non-dense families of complexity classes

Publisher Website
Google Scholar
Abstract
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.

This publication has 5 references indexed in Scilit: