MURAL - Maynooth University Research Archive Library

    RP is Small in SUBEXP else ZPP equals PSPACE and NP equals EXP

    Moser, Philippe (2003) RP is Small in SUBEXP else ZPP equals PSPACE and NP equals EXP. Technical Report. Electronic Colloquium on Computational Complexity.

    Download (214kB) | Preview
    Official URL:

    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...

    Add this article to your Mendeley library


    We use recent results on the hardness of resource-bounded Kolmogorov random strings, to prove that RP is small in SUBEXP else ZPP=PSPACE and NP=EXP. We also prove that if NP is not small in SUBEXP, then NP=AM, improving a former result which held for the measure on E.

    Item Type: Monograph (Technical Report)
    Keywords: kolmogorov randomness; Resource-bounded measure;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Item ID: 10310
    Identification Number: TR03-040
    Depositing User: Philippe Moser
    Date Deposited: 11 Dec 2018 16:42
    Publisher: Electronic Colloquium on Computational Complexity

      Repository Staff Only(login required)

      View Item Item control page


      Downloads per month over past year