• DocumentCode
    3152156
  • Title

    On randomized reductions to sparse sets

  • Author

    Ranjan, Desh ; Rohatgi, Pankaj

  • Author_Institution
    Dept. of Comput. Sci., Cornell Univ., Ithaca, NY, USA
  • fYear
    1992
  • fDate
    22-25 Jun 1992
  • Firstpage
    239
  • Lastpage
    242
  • Abstract
    It is shown that the existence of a sparse set that is hard for the class NP under certain randomized reductions implies that NP=RP and hence all languages in the polynomial-time hierarchy can be recognized feasibly. This provides strong evidence for the nonexistence of such sets
  • Keywords
    computability; computational complexity; NP-hard classes; polynomial-time hierarchy; randomized reductions; sparse sets; Artificial intelligence; Complexity theory; Computer science; Polynomials;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Structure in Complexity Theory Conference, 1992., Proceedings of the Seventh Annual
  • Conference_Location
    Boston, MA
  • Print_ISBN
    0-8186-2955-X
  • Type

    conf

  • DOI
    10.1109/SCT.1992.215397
  • Filename
    215397
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3152156