• DocumentCode
    3152145
  • Title

    How hard are sparse sets?

  • Author

    Hemachandra, Lane A. ; Ogiwara, Mitsunori ; Watanabe, Osamu

  • Author_Institution
    Dept. of Comput. Sci., Rochester Univ., NY, USA
  • fYear
    1992
  • fDate
    22-25 Jun 1992
  • Firstpage
    222
  • Lastpage
    238
  • Abstract
    The frontier of knowledge about the structural properties of sparse sets is explored. A collection of topics that are related to the issue of how hard or easy sparse sets is surveyed. The strongest currently known results, together with the open problems that the results leave, are presented
  • Keywords
    computability; computational complexity; reviews; NP-complete sets; complexity classes; easy; equivalence; hard; lowness; reducibilities; sparse oracles; sparse sets; Approximation algorithms; Circuits; Computer science; Mathematics; 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.215396
  • Filename
    215396
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3152145