MURAL - Maynooth University Research Archive Library



    Martingale Families and Dimension in P


    Moser, Philippe (2008) Martingale Families and Dimension in P. Theoretical Computer Science, 400 (1-3). pp. 46-61. ISSN 0304-3975

    [thumbnail of PM_dimension_in_P.pdf] PDF
    PM_dimension_in_P.pdf

    Download (214kB)

    Abstract

    We introduce a new measure notion on small complexity classes (called F-measure), based on martingale families, that gets rid of some drawbacks of previous measure notions: it can be used to define dimension because martingale families can make money on all strings, and it yields random sequences with an equal frequency of 0’s and 1’s. As applications to F-measure, we answer a question raised in [1] by improving their result to: for almost every language A decidable in subexponential time, PA = BPPA. We show that almost all languages in PSPACE do not have small non-uniform complexity. We compare F-measure to previous notions and prove that martingale families are strictly stronger than Γ-measure [1], we also discuss the limitations of martingale families concerning finite unions. We observe that all classes closed under polynomial many-one reductions have measure zero in EXP iff they have measure zero in SUBEXP. We use martingale families to introduce a natural generalization of Lutz resource-bounded dimension [13] on P, which meets the intuition behind Lutz’s notion. We show that P-dimension lies between finitestate dimension and dimension on E. We prove an analogue to the Theorem of Eggleston in P, i.e. the class of languages whose characteristic sequence contains 1’s with frequency α, has dimension the Shannon entropy of α in P.
    Item Type: Article
    Additional Information: Preprint version of original published article. Moser, P., Martingale families and dimension in P, Theoretical Computer Science, Volume 400, Issues 1–3, 9 June 2008, Pages 46-61, http://www.sciencedirect.com/ http://dx.doi.org/10.1016/j.tcs.2008.02.013
    Keywords: Martingale Families; Dimension; P dimension; small complexity classes;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Item ID: 3502
    Depositing User: Philippe Moser
    Date Deposited: 29 Feb 2012 14:26
    Journal or Publication Title: Theoretical Computer Science
    Publisher: Elsevier
    Refereed: No
    Related URLs:
    URI: https://mural.maynoothuniversity.ie/id/eprint/3502
    Use Licence: This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

    Repository Staff Only (login required)

    Item control page
    Item control page

    Downloads

    Downloads per month over past year

    Origin of downloads