Resource-Bounded Baire Category and Small Circuits in Exponential Space
Jack H. Lutz · 1987
Resource-bounded Baire category is introduced and used to define nontrivial proper ideals of "meager" subsets of E, ESPACE, and other complexity classes. A characterization of these meager sets in terms of resource-bounded infinite games is developed and used to show that only a meager set of languages in ESPACE have polynomial-size circuits.