• DocumentCode
    2931916
  • Title

    The density of weakly complete problems under adaptive reductions

  • Author

    Lutz, Jack H. ; Zhao, Yong

  • Author_Institution
    Dept. of Comput. Sci., Iowa State Univ., Ames, IA, USA
  • fYear
    1997
  • fDate
    24-27 Jun 1997
  • Firstpage
    111
  • Lastpage
    120
  • Abstract
    Given a real number α<1, every language that is weakly ⩽nα/2-TP-hard for E or weakly ⩽nα-TP-hard for E2 is shown to be exponentially dense. This simultaneously strengthens results of J.H. Lutz and E. Mayordomo (1994) and B. Fu (1995)
  • Keywords
    computational complexity; adaptive reductions; computational complexity; real number; weakly complete problems; Circuits; Computational complexity; Computer science; Lifting equipment; Polynomials;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computational Complexity, 1997. Proceedings., Twelfth Annual IEEE Conference on (Formerly: Structure in Complexity Theory Conference)
  • Conference_Location
    Ulm
  • ISSN
    1093-0159
  • Print_ISBN
    0-8186-7907-7
  • Type

    conf

  • DOI
    10.1109/CCC.1997.612306
  • Filename
    612306
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2931916