MURAL - Maynooth University Research Archive Library

    A zero-one law for RP and derandomization of AM if NP is not small

    Impagliazzo, Russell and Moser, Philippe (2009) A zero-one law for RP and derandomization of AM if NP is not small. Information and Computation, 207 (7). pp. 787-792. ISSN 0890-5401

    Download (336kB) | Preview

    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...

    Add this article to your Mendeley library


    We show that if RP does not have p-measure zero then ZPP = EXP. As corollaries we obtain a zero-one law for RP in EXP, and that both probabilistic classes ZPP and RP have the same measure in EXP. We also prove that if NP does not have p-measure zero then NP = AM.

    Item Type: Article
    Additional Information: This is the preprint version of the published article, which is available at DOI: 10.1016/j.ic.2009.02.002
    Keywords: Resource-bounded measure; Derandomization;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Item ID: 8245
    Identification Number:
    Depositing User: Philippe Moser
    Date Deposited: 29 May 2017 14:34
    Journal or Publication Title: Information and Computation
    Publisher: Elsevier
    Refereed: No
    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