Category and measure in complexity classes

• Published in: SIAM journal on computing 1990-12, Vol.19 (6), p.1100-1131
• Main Author: LUTZ, J. H
• Format: Article
• Language: English
• Subjects: Algorithmics. Computability. Computer arithmetics; Applied sciences; Complexity theory; Computer science; control theory; systems; Exact sciences and technology; Investigations; Theoretical computing
• ISSN: 0097-5397; 1095-7111
• DOI: 10.1137/0219076

This paper presents resource-bounded category and resource-bounded measure--two new tools for computational complexity theory--and some applications of these tools to the structure theory of exponential complexity classes. Resource-bounded category, a complexity-theoretic generalization of the Baire category method, defines nontrivial ideals of meager subsets of E, ESPACE, and other complexity classes. Similarly, resource-bounded measure, a generalization of Lebesgue measure theory, defines the measure 0 subsets of complexity classes. Properties developed here include a useful characterization of meager sets in terms of resource-bounded Banach-Mazur games. Resource-bounded category and measure are applied to the investigation of uniform versus nonuniform complexity. Kannan's theorem that $\text{ESPACE} \nsubseteq \text{P}/\text{Poly}$ is extended by showing that ${{{\text{P}}} / {{\text{Poly}}} \cap {\text{ESPACE}}$ is only a meager, measure 0 subset of ESPACE. A theorem of Huynh is extended similarly by showing that all but a meager, measure 0 subset of the languages in {\text{ESPACE}} have high space-bounded Kolmogorov complexity. A new hierarchy of exponential classes is introduced and used to refine known relationships between nonuniform complexity and time complexity. Known properties of hard languages are also extended. Recent results of Schoning and Huynh state that any language $L$ that is $\leqq _m ^{\text{P}}$-hard for E or $\leqq _T ^{\text{P}}$-hard for {\text{ESPACE}} cannot be feasibly approximated. It is proven here that this conclusion in fact holds unless only a meager subset of E is $\leqq _m ^{\text{P}}$-reducible to $L$ and only a meager, measure 0 subset of {\text{ESPACE}} is $\leqq_{m}^{\text{PSPACE}}$ reducible to $L$. This suggests a new lower bound method which may be useful in interesting cases.