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

      Downloads per month over past year

      Origin of downloads