Resource-bounded Baire category: a stronger approach
Stephen Fenner · 2002
The paper introduces a new definition of resource-bounded Baire category in the style of Lutz (1987, 1990, 1992) . This definition gives an almost-all/almost-none theory of various complexity classes. The meagerness/comeagerness of many more classes can be resolved in the new definition than in previous definitions. For example, almost no sets in EXP are EXP-complete, and NP is PF-meager unless NP=EXP. It is also seen under the new definition that no rec-random set can be (recursively) tt-reducible to any PF-generic set. We weaken our definition by putting arbitrary bounds on the length of extension strategies, obtaining a spectrum of different theories of Baire category that includes Lutz's original definition.