MURAL - Maynooth University Research Archive Library

    A zero-one SUBEXP-dimension law for BPP

    Moser, Philippe (2011) A zero-one SUBEXP-dimension law for BPP. Information Processing Letters, 111 (9). pp. 429-432. ISSN 0020-0190

    [img] Download (130kB)

    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...

    Add this article to your Mendeley library


    We show that BPP has either SUBEXP-dimension zero (randomness is easy) or BPP = EXP (randomness is intractable).

    Item Type: Article
    Additional Information: Preprint version of original published article. The definitive version of this article is available at Information Processing Letters (2011) Vol.111 No.9, pp.429–432. DOI:
    Keywords: zero-one; SUBEXP-dimension law; BPP;
    Academic Unit: Faculty of Science and Engineering > Chemistry
    Item ID: 3838
    Depositing User: Philippe Moser
    Date Deposited: 04 Sep 2012 14:35
    Journal or Publication Title: Information Processing Letters
    Publisher: Elsevier
    Refereed: Yes
    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)

    View Item Item control page


    Downloads per month over past year

    Origin of downloads