Moser, Philippe
(2008)
Baire categories on small complexity classes and meager–comeager laws.
Information and Computation, 206 (1).
pp. 1533.
ISSN 08905401
Abstract
We introduce two resourcebounded Baire category notions on small complexity classes such as P, QUASIPOLY, SUBEXP and PSPACE and on probabilistic classes such as BPP, which differ on how the corresponding finite extension strategies are computed. We give an alternative characterization of small sets via resourcebounded BanachMazur games. As an application of the first notion, we show that for almost every language A (i.e. all except a meager class) computable in subexponential time, PA = BPPA. We also show that almost all languages in PSPACE do not have small nonuniform complexity. We then switch to the second Baire category notion (called locallycomputable), and show that the class SPARSE is meager in P. We show that in contrast to the resourcebounded measure case, meager–comeager laws can be obtained for many standard complexity classes, relative to locallycomputable Baire category on BPP and PSPACE. Another topic where locallycomputable Baire categories differ from resourcebounded measure is regarding weakcompleteness: we show that there is no weakcompleteness notion in P based on locallycomputable Baire categories, i.e. every Pweaklycomplete set is complete for P. We also prove that the class of complete sets for P under Turinglogspace reductions is meager in P, if P is not equal to DSPACE (log n), and that the same holds unconditionally for QUASIPOLY. Finally we observe that locallycomputable Baire categories are incomparable with all existing resourcebounded measure notions on small complexity classes, which might explain why those two settings seem to differ so fundamentally.
Item Type: 
Article

Additional Information: 
This is the preprint version of the published article, which is available at DOI: 10.1016/j.ic.2007.10.002 
Keywords: 
Baire categories; 
Academic Unit: 
Faculty of Science and Engineering > Computer Science 
Item ID: 
8242 
Identification Number: 
arXiv:cs/0609012 
Depositing User: 
Philippe Moser

Date Deposited: 
25 May 2017 15:37 
Journal or Publication Title: 
Information and Computation 
Publisher: 
Elsevier 
Refereed: 
Yes 
URI: 

Repository Staff Only(login required)

Item control page 
Downloads per month over past year