MURAL - Maynooth University Research Archive Library



    Baire categories on small complexity classes and meager–comeager laws


    Moser, Philippe (2008) Baire categories on small complexity classes and meager–comeager laws. Information and Computation, 206 (1). pp. 15-33. ISSN 0890-5401

    [img]
    Preview
    Download (271kB) | Preview


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    Abstract

    We introduce two resource-bounded 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 resource-bounded Banach-Mazur 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 locally-computable), and show that the class SPARSE is meager in P. We show that in contrast to the resource-bounded measure case, meager–comeager laws can be obtained for many standard complexity classes, relative to locally-computable Baire category on BPP and PSPACE. Another topic where locally-computable Baire categories differ from resource-bounded measure is regarding weak-completeness: we show that there is no weak-completeness notion in P based on locally-computable Baire categories, i.e. every P-weakly-complete set is complete for P. We also prove that the class of complete sets for P under Turing-logspace 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 locally-computable Baire categories are incomparable with all existing resource-bounded 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)

    View Item Item control page

    Downloads

    Downloads per month over past year