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.

    [img]
    Preview
    Download (214kB) | Preview
    Official URL: https://eccc.weizmann.ac.il/report/2003/040/


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    Abstract

    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
    URI:

      Repository Staff Only(login required)

      View Item Item control page

      Downloads

      Downloads per month over past year