Title :
Resource-bounded Baire category: a stronger approach
Author :
Fenner, Stephen A.
Author_Institution :
Comput. Sci. Dept., Univ. of Southern Maine, Portland, ME, USA
Abstract :
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
Keywords :
category theory; computational complexity; set theory; almost-all/almost-none theory; comeagerness; complexity classes; extension strategies; meagerness; resource-bounded Baire category; Binary sequences; Computer science; Length measurement;
Conference_Titel :
Structure in Complexity Theory Conference, 1995., Proceedings of Tenth Annual IEEE
Conference_Location :
Minneapolis, MN
Print_ISBN :
0-8186-7052-5
DOI :
10.1109/SCT.1995.514856
