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

    [img]
    Preview
    Download (336kB) | Preview


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    Abstract

    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: https://doi.org/10.1016/j.ic.2009.02.002
    Depositing User: Philippe Moser
    Date Deposited: 29 May 2017 14:34
    Journal or Publication Title: Information and Computation
    Publisher: Elsevier
    Refereed: No
    URI:

    Repository Staff Only(login required)

    View Item Item control page

    Downloads

    Downloads per month over past year